package com.my.leetcode;

import com.alibaba.fastjson.JSON;

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;

/**
 *
 */
public class ArrayProblems {


    public static void main(String[] args) {

        ArrayProblems arrayProblems = new ArrayProblems();

        int [] a = {1,2,3,4};
        int [] b = {5,6,7};
        //System.out.println(arrayProblems.findMedianSortedArrays(a,b));
        int [] nums = {0,0,1,1,1,1,2,3,3};
       // System.out.println(arrayProblems.removeDuplicatesII(nums));

        int[] coins = {1,2,5};
        //System.out.println(arrayProblems.coinChange(coins, 11));
        int [] nums2 = {1,2,3,4,12,1,2,3,4,1,1,2,1,1};
        System.out.println(arrayProblems.removeElement(nums2, 1));
        System.out.println(arrayProblems.removeElement(nums2, 3));

    }


    public int[] countPoints(int[][] points, int[][] queries) {

        int qLen = queries.length;
        int [] res = new int[qLen];

        for(int i = 0;i < queries.length;i++){

            int centerX = queries[i][0];
            int centerY = queries[i][1];
            int r = queries[i][2];
            int count = 0;
            for(int j = 0;j < points.length;j++){

                int tmpX = points[j][0];
                int tmpY = points[j][1];
                if(Math.abs(tmpX - centerX) * Math.abs(tmpX - centerX) + Math.abs(tmpY - centerY) * Math.abs(tmpY - centerY) <= r * r){
                    count ++;
                }
            }
            res[i] = count;
        }
        return res;
    }


    /**
     * @author zlx
     * @Description //TODO
     * @Date 4/19/21
     * @Param [nums, val]
     * @return int
     **/
    public int removeElement(int[] nums, int val) {

        if(nums == null || nums.length <= 0){
            return 0;
        }

        int start = 0, len = nums.length;
        int end = len - 1;
        int res = 0;
        while(start <= end){

            if(nums[start] == val && nums[end] != val){
                nums[start] = nums[end];
                nums[end]= val;
                start ++;
                end --;
                res ++;
            }

            if(nums[start] != val){
                start ++;
                res ++;
            }

            if(nums[end] == val){
                end--;
            }
        }
        System.out.println("start is:====" + start + " end ====" + end);
        return res;

    }

    /**
     * @author zlx
     * @Description 26. 删除有序数组中的重复项
     * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。
     *
     * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
     *
     *
     *
     * 说明:
     *
     * 为什么返回数值是整数，但输出的答案是数组呢?
     *
     * 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
     *
     * 你可以想象内部操作如下:
     *
     * // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
     * int len = removeDuplicates(nums);
     *
     * // 在函数里修改输入数组对于调用者是可见的。
     * // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
     * for (int i = 0; i < len; i++) {
     *     print(nums[i]);
     * }
     *
     * 示例 1：
     *
     * 输入：nums = [1,1,2]
     * 输出：2, nums = [1,2]
     * 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
     * 示例 2：
     *
     * 输入：nums = [0,0,1,1,1,2,2,3,3,4]
     * 输出：5, nums = [0,1,2,3,4]
     * 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
     *
     *
     * 提示：
     *
     * 0 <= nums.length <= 3 * 104
     * -104 <= nums[i] <= 104
     * nums 已按升序排列
     * 双指针法
     * @Date 4/9/21
     * @Param [nums]
     * @return int
     **/
    public int removeDuplicatesII(int[] nums) {
        if (nums.length == 0) return 0;
        int i = 0;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
            }
        }
        System.out.println(Arrays.toString(nums));
        return i + 1;
    }


    public int removeDuplicates(int[] nums) {

        int n = nums.length;
        int start = 0;
        int len = 0;
        while(start < n){
            int times = 1;
            int next = start + 1;
            while(next < n && nums[start] == nums[next]){
                nums[next] = Integer.MAX_VALUE;
                next++;
                times++;
            }
            len += times >= 2 ? 1 : times;
            start = next;
        }

        for(int i = 0;i < n;i++){
            System.out.println(nums[i]);
            if(nums[i] == Integer.MAX_VALUE){
                int j = i+1;
                while(j < n && nums[j] == Integer.MAX_VALUE){
                    j++;
                }
                if(j < n){
                    nums[i] = nums[j];
                    nums[j] = Integer.MAX_VALUE;
                }
            }
        }
        System.out.println("len======" + len);
        System.out.println(Arrays.toString(nums));
        return len;
    }

    public int minSubArrayLen(int target, int[] nums) {

        int res = Integer.MAX_VALUE;
        int start = 0, end = 0, n = nums.length;
        int sum = 0;
        while (start < n && end < n){

            sum += nums[end];
            end ++;
            if(sum >= target){
                res = Math.min(res, end - start);
                start++;
                sum = 0;
                end = start;
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }



    /**
     * @author zlx
     * @Description 1004. 最大连续1的个数 III
     * 给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
     *
     * 返回仅包含 1 的最长（连续）子数组的长度。
     *
     *
     *
     * 示例 1：
     *
     * 输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
     * 输出：6
     * 解释：
     * [1,1,1,0,0,1,1,1,1,1,1]
     * 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
     * 示例 2：
     *
     * 输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
     * 输出：10
     * 解释：
     * [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
     * 粗体数字从 0 翻转到 1，最长的子数组长度为 10。
     *
     *
     * 提示：
     *
     * 1 <= A.length <= 20000
     * 0 <= K <= A.length
     * A[i] 为 0 或 1
     *
     * 解题思路： 滑动窗口法进行求解，解题思路同https://leetcode-cn.com/problems/longest-repeating-character-replacement/
     * 同
     * @Date 4/4/21
     * @Param [A, K]
     * @return int
     **/
    public int longestOnes(int[] A, int K) {
        int n = A.length;
        if(n <= K){
            return n;
        }
        int start = 0, end = 0, maxCount = 0;
        int maxLength = 0;

        while(end < n){
            if(A[end] == 1){
                maxCount ++;
            }
            end ++;
            System.out.println("start:" + start + "     end:====" + end + "     maxCount===" + maxCount + "    maxLength===" + maxLength);
            if(end - start > K + maxCount){
                if(A[start] == 1){
                    maxCount --;
                }
                start++;
            }
            maxLength = Math.max(maxLength, end - start);
        }
        return maxLength;
    }

    public List<List<Integer>> pathSum(TreeNode root, int target) {

        path = new ArrayList<>();
        paths = new ArrayList<>();
        if(root == null){
            return paths;
        }

        dfsTree(root, target);
        return paths;
    }


    public List<Integer> path = new ArrayList<>();
    public List<List<Integer>> paths = new ArrayList<>();

    public void dfsTree(TreeNode node, int target){

        path.add(node.val);
        if(node.left == null && node.right == null){
            //System.out.println(path);
            int sum = 0;
            List<Integer> tmpPath = new ArrayList<>(path);
            for(Integer p : tmpPath){
                sum += p;
            }
            if(sum == target){
                paths.add(tmpPath);
            }
            path.remove(path.size() - 1);
            return ;
        }
        if(node.left != null){
            dfsTree(node.left, target);
        }
        if(node.right != null){
            dfsTree(node.right, target);
        }
        path.remove(path.size() - 1);

    }


    /**
     * @author zlx
     * @Description 剑指 Offer 33. 二叉搜索树的后序遍历序列
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
     *
     *
     *
     * 参考以下这颗二叉搜索树：
     *
     *      5
     *     / \
     *    2   6
     *   / \
     *  1   3
     * 示例 1：
     *
     * 输入: [1,6,3,2,5]
     * 输出: false
     * 示例 2：
     *
     * 输入: [1,3,2,6,5]
     * 输出: true
     *
     *
     * 提示：
     *
     * 数组长度 <= 1000
     * @Date 4/3/21
     * @Param [postorder]
     * @return boolean
     **/
    public boolean verifyPostorder(int[] postorder) {

        return verifyPostorder(postorder, 0, postorder.length - 1);

    }

    public boolean verifyPostorder(int [] postorder, int start, int end){

        if(start >= end){
            return true;
        }

        int pivot = postorder[end];

        int i = start;
        while (i < end && postorder[i] < pivot){
            i++;
        }

        for(int j = i;j < end;j++){
            if(postorder[j] < pivot){
                return false;
            }
        }

        return verifyPostorder(postorder, start, i - 1) && verifyPostorder(postorder, i, end - 1);
    }


    /**
     * @author zlx
     * @Description  输入：一个有序数组array，一个整数n输出：如果n在array里，输出n的位置；
     * //如果n不在array中输出n可以插入的位置，插入后的数组仍然有序，例如：
     * //
     * //* [1,3,5,6], 5 → 2
     * //* [1,3,5,6], 2 → 1
     * //* [1,3,5,6], 7 → 4
     * //* [1,3,5,6], 0 → 0
     * //* [1,3,5,6], 4 → 2
     * @Date 4/1/21
     * @Param [array, n]
     * @return int
     **/

    public int getPos(int[] array, int n) {


        if(array[0] > n){
            return 0;
        }

        for(int i = 1;i < array.length;i++){

            if(array[i] >= n){
                return i;
            }
        }

        return array.length;

    }


    /**
     * @author zlx
     * @Description 剑指 Offer 04. 二维数组中的查找
     * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
     *
     *
     *
     * 示例:
     *
     * 现有矩阵 matrix 如下：
     *
     * [
     *   [1,   4,  7, 11, 15],
     *   [2,   5,  8, 12, 19],
     *   [3,   6,  9, 16, 22],
     *   [10, 13, 14, 17, 24],
     *   [18, 21, 23, 26, 30]
     * ]
     * 给定 target = 5，返回 true。
     *
     * 给定 target = 20，返回 false。
     *
     *
     *
     * 限制：
     *
     * 0 <= n <= 1000
     *
     * 0 <= m <= 1000
     * @Date 4/1/21
     * @Param [matrix, target]
     * @return boolean
     **/
    public boolean findNumberIn2DArray(int[][] matrix, int target) {

        if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0){
            return false;
        }

        int row = 0, col = matrix[0].length - 1;
        int rowNums = matrix.length, colNums = matrix[0].length;
        while(row < rowNums && col >= 0){

            int tmpVal = matrix[row][col];
            if(tmpVal > target){
                col --;
            }else if(tmpVal < target){
                row ++;
            }else{
                return true;
            }
        }
        return false;
    }


    /**
     * @author zlx
     * @Description 90. 子集 II
     * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
     *
     * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1,2,2]
     * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
     * 示例 2：
     *
     * 输入：nums = [0]
     * 输出：[[],[0]]
     *
     *
     * 提示：
     *
     * 1 <= nums.length <= 10
     * -10 <= nums[i] <= 10
     * @Date 3/31/21
     * @Param [nums]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    public List<List<Integer>> subsetsWithDup(int[] nums) {

        Arrays.sort(nums);
        res = new ArrayList<>();
        row = new ArrayList<>();
        subsets(0, nums);
        return res;
    }

    public List<List<Integer>> res = new ArrayList<>();
    public List<Integer> row = new ArrayList<>();

    public void subsets(int start, int [] nums){

        List<Integer> tmp = new ArrayList<>(row);
        if(!res.contains(tmp)){
            res.add(tmp);
        }

        if(start >= nums.length){
            return ;
        }

        for(int i = start;i < nums.length;i++){
            row.add(nums[i]);
            subsets(i+1, nums);
            row.remove(row.size() - 1);
        }
    }


    /**
     * @author zlx
     * @Description 18. 四数之和 middle
     * 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
     *
     * 注意：答案中不可以包含重复的四元组。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1,0,-1,0,-2,2], target = 0
     * 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
     * 示例 2：
     *
     * 输入：nums = [], target = 0
     * 输出：[]
     *
     *
     * 提示：
     *
     * 0 <= nums.length <= 200
     * -109 <= nums[i] <= 109
     * -109 <= target <= 109
     * @Date 3/30/21
     * @Param [nums, target]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    public List<List<Integer>> fourSum(int[] nums, int target) {

        if(nums == null || nums.length < 4){
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for(int i = 0;i < n - 3;i++){

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //剪枝
            if(nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target){
                break;
            }

            if(nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target){
                continue;
            }

            for(int j = i+1;j < n - 2;j++){
                if(j > i+1 && nums[j] == nums[j-1]){
                    continue;
                }

                if(nums[i] + nums[j] + nums[j+1] +  nums[j+2] > target){
                    break;
                }

                if(nums[i] + nums[j] + nums[n - 1] + nums[n - 2] < target){
                    continue;
                }
                int left = j + 1, right = n - 1;
                while (left < right){

                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum == target){
                        ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[left] == nums[left + 1]){
                            left ++;
                        }
                        left++;
                        while (left < right && nums[right] == nums[right -1]){
                            right --;
                        }
                        right--;
                    }else if(sum < target){
                        left++;
                    }else{
                        right--;
                    }


                }
            }
        }
        return ans;
    }


    public void setZeroes(int[][] matrix) {

        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return ;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        boolean [] rowsFlag = new boolean[m];
        boolean [] colsFlag = new boolean[n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){

                if(matrix[i][j] == 0){

                    rowsFlag[i] = true;
                    colsFlag[j] = true;
                }
            }
        }

        for(int i = 0;i < m;i++){
            if(rowsFlag[i] == true){
                for(int j = 0;j < n;j++){
                    matrix[i][j] = 0;
                }
            }
        }

        for(int j = 0;j < n;j++){

            if(colsFlag[j]){

                for(int i = 0;i < m;i++){
                    matrix[i][j] = 0;
                }
            }
        }
    }


    /**
     * @author zlx
     * @Description //TODO 
     * @Date 3/20/21
     * @Param [tokens]
     * @return int
     **/
    public int evalRPN(String[] tokens) {

        List<String> operators = Arrays.asList("+", "-", "*", "/");
        Stack<Integer> stack = new Stack<>();
        for(String token : tokens){
            if(operators.contains(token)){

                int b = stack.pop();
                int a = stack.pop();

                int tmpRes = 0;
                if(token.equals("-")){
                    tmpRes = a - b;
                }else if(token.equals("+")){
                    tmpRes = a + b;
                }else if(token.equals("*")){
                    tmpRes = a * b;
                }else{
                    tmpRes = a / b;
                }
                stack.push(tmpRes);
            }else{
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.peek();

    }


    /**
     * @author zlx
     * @Description 59. 螺旋矩阵 II
     * 给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
     * @Date 3/16/21
     * @Param [n]
     * @return int[][]
     **/
    public int[][] generateMatrix(int n) {

        int [][] res = new int[n][n];
        int counts = n % 2 == 0 ? n / 2: (n/2 + 1);
        int val = 1;
        for(int t = 0;t < counts;t++){

            int startX = t, startY = t;

            for(int j = startY;j < n - startY;j++){

                res[startX][j] = val;
                val++;
            }

            for(int i = startX + 1; i < n - startX;i++){
                res[i][n - 1 - startY] = val;
                val++;
            }

            for(int j = n - 2 - startY;j >= startY;j--){
                res[n - 1 - startX][j] = val;
                val ++;
            }

            for(int i = n - 2 - startX;i > startX;i--){
                res[i][startY] = val;
                val ++;
            }
        }
        return res;
    }



    /**
     * @author zlx
     * @Description 1647. 字符频次唯一的最小删除次数
     * 如果字符串 s 中 不存在 两个不同字符 频次 相同的情况，就称 s 是 优质字符串 。
     *
     * 给你一个字符串 s，返回使 s 成为 优质字符串 需要删除的 最小 字符数。
     *
     * 字符串中字符的 频次 是该字符在字符串中的出现次数。例如，在字符串 "aab" 中，'a' 的频次是 2，而 'b' 的频次是 1 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "aab"
     * 输出：0
     * 解释：s 已经是优质字符串。
     * 示例 2：
     *
     * 输入：s = "aaabbbcc"
     * 输出：2
     * 解释：可以删除两个 'b' , 得到优质字符串 "aaabcc" 。
     * 另一种方式是删除一个 'b' 和一个 'c' ，得到优质字符串 "aaabbc" 。
     * 示例 3：
     *
     * 输入：s = "ceabaacb"
     * 输出：2
     * 解释：可以删除两个 'c' 得到优质字符串 "eabaab" 。
     * 注意，只需要关注结果字符串中仍然存在的字符。（即，频次为 0 的字符会忽略不计。）
     *
     *
     * 提示：
     *
     * 1 <= s.length <= 105
     * s 仅含小写英文字母
     * @Date 3/15/21
     * @Param [s]
     * @return int
     **/
    public int minDeletions(String s) {


        int [] sArray = new int[26];
        for(int i = 0;i < s.length();i++){
            sArray[s.charAt(i) - 'a']++;
        }

        int res = 0;
        Arrays.sort(sArray);
        for(int i = 24;i >= 0;i --){

            if(sArray[i] == 0){
                continue;
            }
            if(sArray[i] >= sArray[i+1]){
                int delta = sArray[i+1] - 1 >= 0 ? sArray[i+1] - 1 : 0;
                res += sArray[i] - delta;
                sArray[i] = delta;
            }
        }
        return res;

    }




    /**
     * @author zlx
     * @Description 1711. 大餐计数
     * 大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。
     *
     * 你可以搭配 任意 两道餐品做一顿大餐。
     *
     * 给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i​​​​​​​​​​​​​​ 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 10^9 + 7 取余。
     *
     * 注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。
     *
     *
     *
     * 示例 1：
     *
     * 输入：deliciousness = [1,3,5,7,9]
     * 输出：4
     * 解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
     * 它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。
     * 示例 2：
     *
     * 输入：deliciousness = [1,1,1,3,3,3,7]
     * 输出：15
     * 解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。
     *
     *
     * 提示：
     *
     * 1 <= deliciousness.length <= 10^5
     * 0 <= deliciousness[i] <= 2^20
     * @Date 1/28/21
     * @Param [deliciousness]
     * @return int
     **/
    public int countPairs(int[] deliciousness) {

        Map<Integer, Integer> map = new HashMap<>();
        long res = 0;
        for(int delicious : deliciousness){


            for(int i = 0;i <= 21;i++){

                int sum = (int) Math.pow(2, i);
                if(map.containsKey(sum - delicious)){
                    res += map.get(sum - delicious);
                }
            }

            map.put(delicious, map.getOrDefault(delicious, 0 ) + 1);
        }
        //res = (int)(res % (1e9 + 7));
        res %= (1e9 + 7);
        return (int)res;
    }


    /**
     * @author zlx
     * @Description 724. 寻找数组的中心索引 easy
     * 给你一个整数数组 nums，请编写一个能够返回数组 “中心索引” 的方法。
     *
     * 数组 中心索引 是数组的一个索引，其左侧所有元素相加的和等于右侧所有元素相加的和。
     *
     * 如果数组不存在中心索引，返回 -1 。如果数组有多个中心索引，应该返回最靠近左边的那一个。
     *
     * 注意：中心索引可能出现在数组的两端。
     *
     *
     *
     * 示例 1：
     *
     * 输入：nums = [1, 7, 3, 6, 5, 6]
     * 输出：3
     * 解释：
     * 索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11)，与右侧数之和 (5 + 6 = 11) 相等。
     * 同时, 3 也是第一个符合要求的中心索引。
     * 示例 2：
     *
     * 输入：nums = [1, 2, 3]
     * 输出：-1
     * 解释：
     * 数组中不存在满足此条件的中心索引。
     * 示例 3：
     *
     * 输入：nums = [2, 1, -1]
     * 输出：0
     * 解释：
     * 索引 0 左侧不存在元素，视作和为 0 ；右侧数之和为 1 + (-1) = 0 ，二者相等。
     * 示例 4：
     *
     * 输入：nums = [0, 0, 0, 0, 1]
     * 输出：4
     * 解释：
     * 索引 4 左侧数之和为 0 ；右侧不存在元素，视作和为 0 ，二者相等。
     *
     *
     * 提示：
     *
     * nums 的长度范围为 [0, 10000]。
     * 任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。
     * @Date 1/28/21
     * @Param [nums]
     * @return int
     **/
    public int pivotIndex(int[] nums) {

        if(nums == null || nums.length <= 0)
            return -1;
        int [] sum = new int[nums.length + 1];
        for(int i = 0;i < nums.length;i++){
            sum[i + 1] = sum[i] + nums[i];
        }

        for(int i = 1;i <= nums.length;i++){

            int left = sum[i-1];
            int right = sum[nums.length] - sum[i];
            if(left == right){
                return i - 1;
            }
        }
        return  -1;
    }


    /**
     * @author zlx
     * @Description 1319. 连通网络的操作次数
     * 用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
     *
     * 网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
     *
     * 给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。
     *
     *
     *
     * 示例 1：
     *
     *
     *
     * 输入：n = 4, connections = [[0,1],[0,2],[1,2]]
     * 输出：1
     * 解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。
     * 示例 2：
     *
     *
     *
     * 输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
     * 输出：2
     * 示例 3：
     *
     * 输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
     * 输出：-1
     * 解释：线缆数量不足。
     * 示例 4：
     *
     * 输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
     * 输出：0
     *
     *
     * 提示：
     *
     * 1 <= n <= 10^5
     * 1 <= connections.length <= min(n*(n-1)/2, 10^5)
     * connections[i].length == 2
     * 0 <= connections[i][0], connections[i][1] < n
     * connections[i][0] != connections[i][1]
     * 没有重复的连接。
     * 两台计算机不会通过多条线缆连接。
     *
     * 解题思路： 并查集
     * @Date 1/25/21
     * @Param [n, connections]
     * @return int
     **/
    public int makeConnected(int n, int[][] connections) {

        int row = connections.length;
        if(row < (n - 1)){
            return -1;
        }

        UnionFind2 unionFind2 = new UnionFind2(n);
        for(int i = 0;i < connections.length;i++){
            unionFind2.union(connections[i][0], connections[i][1]);
        }

        return unionFind2.setCount - 1;

    }


    public class UnionFind2{

        private int [] parent;
        private int [] size;
        //当前连通分量个数
        private int setCount;


        public UnionFind2(int n){

            this.size = new int[n];
            this.parent = new int[n];
            this.setCount = n;
            for(int i = 0;i < n;i++){
                parent[i] = i;
                size[i] = 1;
            }
        }

        public void union(int x, int y){

            int idx = find(x);
            int idY = find(y);

            if(idx == idY){
                return ;
            }

            if (size[idx] == size[idY]) {
                parent[idx] = idY;
                // 此时以 rootY 为根结点的树的高度仅加了 1
                size[idx]++;
            } else if (size[idx] < size[idY]) {
                parent[idx] = idY;
                // 此时以 rootY 为根结点的树的高度不变
            } else {
                // 同理，此时以 rootX 为根结点的树的高度不变
                parent[idY] = idY;
            }
            setCount --;
        }

        public int find(int x){

            if(parent[x] == x){
                return x;
            }else{
                return find(parent[x]);
            }
        }
    }


    /**
     * @author zlx
     * @Description 1128. 等价多米诺骨牌对的数量easy
     * 给你一个由一些多米诺骨牌组成的列表 dominoes。
     *
     * 如果其中某一张多米诺骨牌可以通过旋转 0 度或 180 度得到另一张多米诺骨牌，我们就认为这两张牌是等价的。
     *
     * 形式上，dominoes[i] = [a, b] 和 dominoes[j] = [c, d] 等价的前提是 a==c 且 b==d，或是 a==d 且 b==c。
     *
     * 在 0 <= i < j < dominoes.length 的前提下，找出满足 dominoes[i] 和 dominoes[j] 等价的骨牌对 (i, j) 的数量。
     *
     *
     *
     * 示例：
     *
     * 输入：dominoes = [[1,2],[2,1],[3,4],[5,6]]
     * 输出：1
     *
     *
     * 提示：
     *
     * 1 <= dominoes.length <= 40000
     * 1 <= dominoes[i][j] <= 9
     * @Date 1/26/21
     * @Param [dominoes]
     * @return int
     **/
    public int numEquivDominoPairs(int[][] dominoes) {

        for(int i = 0;i < dominoes.length;i++){
            if(dominoes[i][0] > dominoes[i][1]){
                int tmp = dominoes[i][0];
                dominoes[i][0] = dominoes[i][1];
                dominoes[i][1] = tmp;
            }
        }

        Arrays.sort(dominoes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] != o2[0]){
                    return o1[0] - o2[0];
                }else{
                    return o1[1] - o2[1];
                }
            }
        });
        int nums = 1;
        int res = 0;
        for(int i = 1;i < dominoes.length;i++){

            if(dominoes[i-1][0] == dominoes[i][0] && dominoes[i-1][1] == dominoes[i][1]){
                nums ++;
            }else{
                res += (nums - 1) * nums / 2;
                nums = 1;
            }
        }
        res += (nums - 1) * nums / 2;
        return res;
    }



    /**
     * @author zlx
     * @Description 最长连续递增子序列 easy
     * @Date 1/25/21
     * @Param [nums]
     * @return int
     **/
    public int findLengthOfLCIS(int[] nums) {

        if(nums == null || nums.length <= 1){
            return 0;
        }

        int longest = 1, n = nums.length, res = 1;
        for(int i = 1;i < n;i++){

            if(nums[i] > nums[i-1]){
                longest ++;
            }else{
                res = Math.max(res, longest);
                longest = 1;
            }
        }
        res = Math.max(res, longest);
        return res;
    }

    /**
     * @author zlx
     * @Description 628. 三个数的最大乘积easy
     * 给定一个整型数组，在数组中找出由三个数组成的最大乘积，并输出这个乘积。
     *
     * 示例 1:
     *
     * 输入: [1,2,3]
     * 输出: 6
     * 示例 2:
     *
     * 输入: [1,2,3,4]
     * 输出: 24
     * 注意:
     *
     * 给定的整型数组长度范围是[3,104]，数组中所有的元素范围是[-1000, 1000]。
     * 输入的数组中任意三个数的乘积不会超出32位有符号整数的范围。
     * @Date 1/20/21
     * @Param [nums]
     * @return int
     **/
    public int maximumProduct(int[] nums) {

        Arrays.sort(nums);
        int len = nums.length;
        return Math.max(nums[len - 1] * nums[len-2] * nums[len-3], nums[len - 1] * nums[0] * nums[1]);
    }


    /**
     * @author zlx
     * @Description 189. 旋转数组 middle
     * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
     *
     * 示例 1:
     *
     * 输入: [1,2,3,4,5,6,7] 和 k = 3
     * 输出: [5,6,7,1,2,3,4]
     * 解释:
     * 向右旋转 1 步: [7,1,2,3,4,5,6]
     * 向右旋转 2 步: [6,7,1,2,3,4,5]
     * 向右旋转 3 步: [5,6,7,1,2,3,4]
     * 示例 2:
     *
     * 输入: [-1,-100,3,99] 和 k = 2
     * 输出: [3,99,-1,-100]
     * 解释:
     * 向右旋转 1 步: [99,-1,-100,3]
     * 向右旋转 2 步: [3,99,-1,-100]
     * 说明:
     *
     * 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
     * 要求使用空间复杂度为 O(1) 的 原地 算法。
     * @Date 1/11/21
     * @Param [nums, k]
     * @return void
     **/
    public void rotate(int[] nums, int k) {

        if(nums == null || nums.length <= 0 || k == 0){
            return ;
        }
        int len = nums.length;
        int move = k % len;
        int [] copy = new int[len];
        for(int i = 0;i < len;i++){
            copy[i] = nums[i];
        }

        for(int i = 0;i < len;i++){
            nums[(i + move) % len] = copy[i];
        }
    }


    public int findCircleNum(int[][] isConnected) {

        int n = isConnected.length;
        if(n == 1){
            return 1;
        }
        boolean [] isVisited = new boolean[n];
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0;i < n;i++){
            if(!isVisited[i]){
                queue.add(i);
                while (!queue.isEmpty()){
                    int j = queue.poll();
                    isVisited[j] = true;
                    for(int k = 0;k < n;k++){
                        if(isConnected[j][k] == 1 && isVisited[k] == false){
                            queue.add(k);
                        }
                    }
                }
                count++;
            }
        }
        return count;
    }






    /*public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

        double [] res = new double[queries.size()];


    }*/

    /**
     * @author zlx
     * @Description
     * @Date 1/5/21
     * @Param [nums, l, r]
     * @return java.util.List<java.lang.Boolean>
     **/
    public List<Boolean> checkArithmeticSubarrays(int[] nums, int[] l, int[] r) {

        int m = l.length;

        List<Boolean> res = new ArrayList<>();
        for(int i = 0;i < m;i++){
            int start = l[i];
            int end = r[i];
            if(start > end || (end - start + 1) < 2){
                res.add(false);
                continue;
            }

            int [] tmp = new int[end - start + 1];
            for(int j = start;j <= end;j++){
                tmp[j-start] = nums[j];
            }
            System.out.println("=====" + Arrays.toString(tmp));
            res.add(isArithmeticSequence(tmp));
        }
        return res;

    }


    public boolean isArithmeticSequence(int [] array){

        Arrays.sort(array);
        int cha = array[1] - array[0];
        for(int i = 2;i < array.length;i++){
            if(array[i] - array[i-1] != cha){
                return false;
            }
        }
        return true;
    }


    /**
     * @author zlx
     * @Description 56. 合并区间 middle
     * 给出一个区间的集合，请合并所有重叠的区间。
     *
     *
     *
     * 示例 1:
     *
     * 输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
     * 输出: [[1,6],[8,10],[15,18]]
     * 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
     * 示例 2:
     *
     * 输入: intervals = [[1,4],[4,5]]
     * 输出: [[1,5]]
     * 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
     * 注意：输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。
     *
     *
     *
     * 提示：
     *
     * intervals[i][0] <= intervals[i][1]
     * @Date 2020-12-30
     * @Param [intervals]
     * @return int[][]
     **/
    public int[][] merge(int[][] intervals) {

        if(intervals == null || intervals.length <= 0){
            return new int[][]{};
        }
        if(intervals.length == 1){
            return intervals;
        }
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        List<int []> res = new ArrayList<>();
        for(int i = 0;i < intervals.length;i++){

            if(res.size() == 0){
                res.add(new int[]{intervals[i][0], intervals[i][1]});
            }else{

                int [] last = res.get(res.size() - 1);
                int left = last[0], right = last[1];
                int start = intervals[i][0];
                int end = intervals[i][1];
                if(start >= left && start <= right){
                    res.remove(res.size() - 1);
                    res.add( new int []{Math.min(start, left), Math.max(right, end)});
                }else{
                    res.add(new int[]{start, end});
                }
            }
        }
        int [][] result = new int[res.size()][2];
        for(int i = 0;i < res.size();i++){
            result[i] = res.get(i);
        }
        //return result;
        return res.toArray(new int[res.size()][]);
    }


    /**
     * @author zlx
     * @Description 378. 有序矩阵中第K小的元素
     * 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
     * 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。
     *
     *
     *
     * 示例：
     *
     * matrix = [
     *    [ 1,  5,  9],
     *    [10, 11, 13],
     *    [12, 13, 15]
     * ],
     * k = 8,
     *
     * 返回 13。
     *
     *
     * 提示：
     * 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2
     *
     *
     * @Date 2020-12-30
     * @Param [matrix, k]
     * @return int
     **/
    public int kthSmallest(int[][] matrix, int k) {

        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n-1][n-1];

        while (left < right){
            int middle = (left + right) >> 1;
            if(checkSum(matrix, middle, k)){
                right = middle;
            }else {
                left = middle + 1;
            }
        }
        return left;

    }

    //计算矩阵中小于等于
    public boolean checkSum(int [][] matrix, int val, int k){

        int sum = 0;
        int i = matrix.length - 1, j = 0;

        while (i >= 0 && j < matrix.length){
            if(matrix[i][j] <= val){
                j++;
                sum += i+1;
            }else{
                i --;
            }
        }
        return sum >= k;
    }

    /**
     * @author zlx
     * @Description 455. 分发饼干 easy
     * 假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
     *
     * 对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
     *
     *
     * 示例 1:
     *
     * 输入: g = [1,2,3], s = [1,1]
     * 输出: 1
     * 解释:
     * 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
     * 虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
     * 所以你应该输出1。
     * 示例 2:
     *
     * 输入: g = [1,2], s = [1,2,3]
     * 输出: 2
     * 解释:
     * 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
     * 你拥有的饼干数量和尺寸都足以让所有孩子满足。
     * 所以你应该输出2.
     *
     *
     * 提示：
     *
     * 1 <= g.length <= 3 * 104
     * 0 <= s.length <= 3 * 104
     * 1 <= g[i], s[j] <= 231 - 1
     * @Date 2020-12-25
     * @Param [g, s]
     * @return int
     **/
    public int findContentChildren(int[] g, int[] s) {

        Arrays.sort(g);
        Arrays.sort(s);

        int count = 0;
        int gIndex = 0, sIndex = 0;
        while (gIndex < g.length && sIndex < s.length) {

            while (sIndex < s.length && s[sIndex] < g[gIndex]){
                sIndex++;
            }
            if(sIndex < s.length){
                count++;

            }
            sIndex++;
            gIndex++;
        }

        return count;
    }


    /**
     * @author zlx
     * @Description 1477. 找两个和为目标值且不重叠的子数组 middle
     * 给你一个整数数组 arr 和一个整数值 target 。
     *
     * 请你在 arr 中找 两个互不重叠的子数组 且它们的和都等于 target 。可能会有多种方案，请你返回满足要求的两个子数组长度和的 最小值 。
     *
     * 请返回满足要求的最小长度和，如果无法找到这样的两个子数组，请返回 -1 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：arr = [3,2,2,4,3], target = 3
     * 输出：2
     * 解释：只有两个子数组和为 3 （[3] 和 [3]）。它们的长度和为 2 。
     * 示例 2：
     *
     * 输入：arr = [7,3,4,7], target = 7
     * 输出：2
     * 解释：尽管我们有 3 个互不重叠的子数组和为 7 （[7], [3,4] 和 [7]），但我们会选择第一个和第三个子数组，因为它们的长度和 2 是最小值。
     * 示例 3：
     *
     * 输入：arr = [4,3,2,6,2,3,4], target = 6
     * 输出：-1
     * 解释：我们只有一个和为 6 的子数组。
     * 示例 4：
     *
     * 输入：arr = [5,5,4,4,5], target = 3
     * 输出：-1
     * 解释：我们无法找到和为 3 的子数组。
     * 示例 5：
     *
     * 输入：arr = [3,1,1,1,5,1,2,1], target = 3
     * 输出：3
     * 解释：注意子数组 [1,2] 和 [2,1] 不能成为一个方案因为它们重叠了。
     *
     *
     * 提示：
     *
     * 1 <= arr.length <= 10^5
     * 1 <= arr[i] <= 1000
     * 1 <= target <= 10^8
     * 解法一： 使用Hashmap求解
     * 解法二： 滑动窗口求解
     * 解法三： 动态规划求解
     * @Date 2020-12-24
     * @Param [arr, target]
     * @return int
     **/
    public int minSumOfLengths(int[] arr, int target) {

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int sum = 0, llen = Integer.MAX_VALUE, res = Integer.MAX_VALUE;
        for(int i = 0;i < arr.length;i++){
            sum += arr[i];
            map.put(sum, i);
        }
        sum = 0;
        for(int i = 0;i < arr.length;i++){
            sum += arr[i];
            //求最短和为target的长度
            if(map.containsKey(sum - target)){
                llen = Math.min(llen, i - map.get(sum - target));
            }

            //从i+1开始查找下一个和=target的子树组
            if(map.containsKey(sum + target) && llen < Integer.MAX_VALUE){
                //更新最短子树组长度和
                res = Math.min(res, map.get(sum + target) - i + llen);
            }
        }

        //System.out.println("llen is:=====" + llen + "    res is: =====" + res);
        return res == Integer.MAX_VALUE ? -1 : res;

    }

    /**
     * @author zlx
     * @Description 135. 分发糖果 hard
     * 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
     *
     * 你需要按照以下要求，帮助老师给这些孩子分发糖果：
     *
     * 每个孩子至少分配到 1 个糖果。
     * 相邻的孩子中，评分高的孩子必须获得更多的糖果。
     * 那么这样下来，老师至少需要准备多少颗糖果呢？
     *
     * 示例 1:
     *
     * 输入: [1,0,2]
     * 输出: 5
     * 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
     * 示例 2:
     *
     * 输入: [1,2,2]
     * 输出: 4
     * 解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
     *      第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
     *
     * 解题思路：根据题意，分成左右2个规则，2次遍历
     *          左规则当 ratings[i-1] < ratings[i], 同学i的糖果数量比同学i-1要多，否则同学i糖果数置为1
     *          右规则当 ratings[i] > ratings[i+1], 同学i的糖果树比同学i+1要多， 否则同学i糖果数置为1
     *          2次遍历后，通过i的糖果数是 max(left[i], right[i])
     *
     * @Date 2020-12-24
     * @Param [ratings]
     * @return int
     **/
    public int candy(int[] ratings) {

        if(ratings == null || ratings.length <= 0){
            return 0;
        }

        int [] left = new int[ratings.length];
        left[0] = 1;
        for(int i = 1;i < left.length;i++){
            if(ratings[i] > ratings[i-1]){
                left[i] = left[i-1] + 1;
            }else{
                left[i] = 1;
            }
        }

        int right = 1;
        int res = Math.max(right, left[ratings.length - 1]);
        for(int j = ratings.length - 2;j >= 0;j--){
            if(ratings[j] > ratings[j+1]){
                right = right + 1;
            }else{
                right = 1;
            }
            res += Math.max(right, left[j]);
        }

        return res;

    }


    /**
     * @author zlx
     * @Description 48. 旋转图像 middle
     * 给定一个 n × n 的二维矩阵表示一个图像。
     *
     * 将图像顺时针旋转 90 度。
     *
     * 说明：
     *
     * 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
     *
     * 示例 1:
     *
     * 给定 matrix =
     * [
     *   [1,2,3],
     *   [4,5,6],
     *   [7,8,9]
     * ],
     *
     * 原地旋转输入矩阵，使其变为:
     * [
     *   [7,4,1],
     *   [8,5,2],
     *   [9,6,3]
     * ]
     * 示例 2:
     *
     * 给定 matrix =
     * [
     *   [ 5, 1, 9,11],
     *   [ 2, 4, 8,10],
     *   [13, 3, 6, 7],
     *   [15,14,12,16]
     * ],
     *
     * 原地旋转输入矩阵，使其变为:
     * [
     *   [15,13, 2, 5],
     *   [14, 3, 4, 1],
     *   [12, 6, 8, 9],
     *   [16, 7,10,11]
     * ]
     *
     *  核心是： matrix[i][j] 旋转之后， 坐标为matrix[j][n-1-i]
     * @Date 2020-12-21
     * @Param [matrix]
     * @return void
     **/
    public void rotateI(int[][] matrix) {

        if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0){
            return ;
        }
        int n = matrix.length;
        int [][] newMatrix = new int[n][n];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                newMatrix[j][n - 1 - i] = matrix[i][j];
            }
        }

        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                matrix[i][j] = newMatrix[i][j];
            }
        }

    }



    /**
     * @author zlx
     * @Description 659. 分割数组为连续子序列 middle
     * 给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。
     *
     * 如果可以完成上述分割，则返回 true ；否则，返回 false 。
     *
     *
     *
     * 示例 1：
     *
     * 输入: [1,2,3,3,4,5]
     * 输出: True
     * 解释:
     * 你可以分割出这样两个连续子序列 :
     * 1, 2, 3
     * 3, 4, 5
     *
     *
     * 示例 2：
     *
     * 输入: [1,2,3,3,4,4,5,5]
     * 输出: True
     * 解释:
     * 你可以分割出这样两个连续子序列 :
     * 1, 2, 3, 4, 5
     * 3, 4, 5
     *
     *
     * 示例 3：
     *
     * 输入: [1,2,3,4,4,5]
     * 输出: False
     *
     * 解题思路： 基于哈希表+最小堆栈求解，Map<Integer, PriorityQueue<Integer>> key表示以key结尾的连续子序列，PriorityQueue<Integer> 存放以key结尾的连续子序列的长度，栈顶元素是最小长度；
     * 遍历到x，判断x-1结尾的子序列属否存在，存在，最短的长度+1为以x结尾的连续子序列长度，放入到map中， 以x-1结尾的长度少掉一个；
     * 最后，判断长度是否均大于3即可
     *
     * 提示：
     *
     * 输入的数组长度范围为 [1, 10000]
     * @Date 2020-12-07
     * @Param [nums]
     * @return boolean
     **/
    public boolean isPossible(int[] nums) {

        if(nums == null || nums.length < 3){
            return false;
        }

        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        for(int num : nums){

            if(!map.containsKey(num)){
                map.put(num, new PriorityQueue<>());
            }

            if(map.containsKey(num - 1)){
                int len = map.get(num - 1).poll();
                if(map.get(num - 1).isEmpty()){
                    map.remove(num - 1);
                }
                map.get(num).offer(len + 1);
            }else {
                map.get(num).offer(1);
            }
        }

        for(Map.Entry<Integer, PriorityQueue<Integer>> entry : map.entrySet()){
            if(entry.getValue().peek() < 3){
                return false;
            }
        }
        return true;
    }


    /**
     * @author zlx
     * @Description 321. 拼接最大数
     * 给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。
     *
     * 求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。
     *
     * 说明: 请尽可能地优化你算法的时间和空间复杂度。
     *
     * 示例 1:
     *
     * 输入:
     * nums1 = [3, 4, 6, 5]
     * nums2 = [9, 1, 2, 5, 8, 3]
     * k = 5
     * 输出:
     * [9, 8, 6, 5, 3]
     * 示例 2:
     *
     * 输入:
     * nums1 = [6, 7]
     * nums2 = [6, 0, 4]
     * k = 5
     * 输出:
     * [6, 7, 6, 0, 4]
     * 示例 3:
     *
     * 输入:
     * nums1 = [3, 9]
     * nums2 = [8, 9]
     * k = 3
     * 输出:
     * [9, 8, 9]
     * @Date 2020-12-03
     * @Param [nums1, nums2, k]
     * @return int[]
     **/
    public int[] maxNumber(int[] nums1, int[] nums2, int k) {


        int [] res = new int[k];
        for(int i = 0;i <= k;i++){
            if(i <= nums1.length && k-i <= nums2.length) {
                System.out.println("nums1's k:" + i +  "   nums's k" + (k-i));
                int[] tmp = merge(getMaxArray(nums1, i), getMaxArray(nums2, k - i));
                System.out.println("=========merget result is:====" + Arrays.toString(tmp));
                res = compareMaxArray(tmp, res);
            }
        }

        return res;
    }
    
    public int [] compareMaxArray(int [] a, int []b){
        
        for(int i = 0;i < a.length;i++){
            
            if(a[i] < b[i]){
                return b;
            }else if(a[i] > b[i]){
                return a;
            }
        }
        return a;
    }

    public int [] merge(int [] nums1, int [] nums2){

        int[] res = new int[nums1.length+nums2.length];
        int cur = 0;
        int p1 = 0;
        int p2 = 0;
        // 这里原来两个数组未必有序，为了让大的元素尽可能往前放，比较的时候若当前元素相等还要往后比较
        while(p1<nums1.length||p2<nums2.length){
            if(compare(nums1, p1, nums2, p2)){
                res[cur++] = nums1[p1++];
            }else{
                res[cur++] = nums2[p2++];
            }
        }
        return res;
    }

    private boolean compare(int[] nums1, int p1, int[] nums2, int p2){
        if(p2>=nums2.length) return true;
        if(p1>=nums1.length) return false;
        if(nums1[p1]>nums2[p2]) return true;
        if(nums1[p1]<nums2[p2]) return false;
        return compare(nums1, p1+1, nums2, p2+1);
    }

    //保留k个字符最大值
    public int [] getMaxArray(int [] nums, int k){

        if(k == 0){
            return new int []{};
        }

        int deleteNum = nums.length - k;
        Stack<Integer> stack = new Stack<>();
        stack.add(nums[0]);
        for(int i = 1;i < nums.length;i++){
            while (!stack.isEmpty() && deleteNum > 0 && stack.peek() < nums[i]){
                stack.pop();
                deleteNum --;
            }
            stack.push(nums[i]);
        }
        Integer [] arrays = stack.toArray(new Integer [stack.size()]);
        System.out.println("=====" + Arrays.toString(arrays));
        int [] res = new int [k];
        int index = 0;
        for(int i = 0;i < res.length;i++){
            //if(arrays[index] != 0){
                res[i] = arrays[index++];

            //}
        }
        System.out.println(Arrays.toString(nums) + " getMaxArray of "+ k  + "   " + Arrays.toString(res));
        return res;
    }


    /**
     * @author zlx
     * @Description 剑指 Offer 10- II. 青蛙跳台阶问题
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
     *
     * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
     *
     * 示例 1：
     *
     * 输入：n = 2
     * 输出：2
     * 示例 2：
     *
     * 输入：n = 7
     * 输出：21
     * 示例 3：
     *
     * 输入：n = 0
     * 输出：1
     * 提示：
     *
     * 0 <= n <= 100
     * 注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbing-stairs/
     *
     *
     * @Date 2020-12-01
     * @Param [n]
     * @return int
     **/
    public int numWays(int n) {

        int [] res = new int[n+1];
        res[0] = 0;
        res[1] = 1;
        res[2] = 2;
        for(int i = 3;i <= n;i++){
            res[i] = (res[i-1] + res[i - 2])%1000000007;
        }
        return res[n];
    }


    /**
     * @author zlx
     * @Description 34. 在排序数组中查找元素的第一个和最后一个位置
     * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
     *
     * 如果数组中不存在目标值 target，返回 [-1, -1]。
     *
     * 进阶：
     *
     * 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
     *
     * 进阶实现方式： 有序数组，可以使用二分查找法
     *
     *
     * 示例 1：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 8
     * 输出：[3,4]
     * 示例 2：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 6
     * 输出：[-1,-1]
     * 示例 3：
     *
     * 输入：nums = [], target = 0
     * 输出：[-1,-1]
     *
     *
     * 提示：
     *
     * 0 <= nums.length <= 105
     * -109 <= nums[i] <= 109
     * nums 是一个非递减数组
     * -109 <= target <= 109
     * @Date 2020-12-01
     * @Param [nums, target]
     * @return int[]
     **/
    public int[] searchRange(int[] nums, int target) {

        if(nums == null || nums.length <= 0){
            return new int []{-1,-1};
        }

        int start = -1, end = -1;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){

            if(nums[i] == target){

                if(start == -1){
                    start = i;
                }else{
                    end = i;
                }
            }
        }
        if(start != -1 && end == -1){
            end = start;
        }
        return new int [] {start, end};
    }


    //基于二分查找查询
    public int[] searchRangeII(int[] nums, int target) {

        if(nums == null || nums.length <= 0){
            return new int []{-1,-1};
        }

        int start = binarySort(nums, target, true);
        int end = binarySort(nums, target, false);
        if(start <= end && end < nums.length && nums[end] == target && nums[start] == target){
            return new int [] {start, end};
        }
        return new int []{-1,-1};
    }


    public int binarySort(int [] nums, int target, boolean flag){

        int start = 0, end = nums.length - 1;
        int ans = nums.length;
        while (start <= end){

            int middle = (start + end)/2;
            if(nums[middle] > target || (flag && nums[middle] >= target)){
                end = middle - 1;
                ans = middle;
            }else{
                start = middle + 1;
            }

        }
        return ans;

    }

    /**
     * @author zlx
     * @Description 976. 三角形的最大周长 easy
     * 给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。
     *
     * 如果不能形成任何面积不为零的三角形，返回 0。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[2,1,2]
     * 输出：5
     * 示例 2：
     *
     * 输入：[1,2,1]
     * 输出：0
     * 示例 3：
     *
     * 输入：[3,2,3,4]
     * 输出：10
     * 示例 4：
     *
     * 输入：[3,6,2,3]
     * 输出：8
     *
     *
     * 提示：
     *
     * 3 <= A.length <= 10000
     * 1 <= A[i] <= 10^6
     * @Date 2020-11-30
     * @Param [A]
     * @return int
     **/
    public int largestPerimeter(int[] A) {

        if(A == null || A.length < 3){
            return 0;
        }

        Arrays.sort(A);

        int len = A.length;

        for(int i = len - 1;i >=2;i--){

            if(A[i] < A[i-1] + A[i-2]){
                return A[i] + A[i-1] + A[i-2];
            }
        }

        return 0;

    }

    /**
     * @author zlx
     * @Description 493. 翻转对 hard
     * 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
     *
     * 你需要返回给定数组中的重要翻转对的数量。
     *
     * 示例 1:
     *
     * 输入: [1,3,2,3,1]
     * 输出: 2
     * 示例 2:
     *
     * 输入: [2,4,3,5,1]
     * 输出: 3
     * 注意:
     *
     * 给定数组的长度不会超过50000。
     * 输入数组中的所有数字都在32位整数的表示范围内。
     * @Date 2020-11-28
     * @Param [nums]
     * @return int
     **/
    public int reversePairs(int[] nums) {

        return 0;

    }

    //解法一：暴力破解法，但是会超时
    public int reversePairsSolutionI(int[] nums) {

        int count = 0;
        for(int i = 0;i < nums.length;i++){

            for(int j = i+1;j < nums.length;j++){

                if(nums[j] < (nums[i] / 2.0)){
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * @author zlx
     * @Description 454. 四数相加 II middle
     * 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
     *
     * 为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。
     *
     * 例如:
     *
     * 输入:
     * A = [ 1, 2]
     * B = [-2,-1]
     * C = [-1, 2]
     * D = [ 0, 2]
     *
     * 输出:
     * 2
     *
     * 解题思路：分组+hash， A+B两两相加，放入hashmap， C+D俩俩相加，hashmap
     *
     * 解释:
     * 两个元组如下:
     * 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
     * 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0
     * @Date 2020-11-27
     * @Param [A, B, C, D]
     * @return int
     **/
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {

        if(A.length == 0){
            return 0;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for(int a: A){
            for(int b : B){
                map.put(a + b, map.getOrDefault(a + b, 0) + 1);
            }
        }

        int ans = 0;
        for(int c : C){
            for(int d : D){
                if(map.containsKey(-c-d)){
                    ans += map.get(-c-d);
                }
            }
        }
        return ans;
    }


    /**
     * @author zlx
     * @Description 164. 最大间距 middle
     * 给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。
     *
     * 如果数组元素个数小于 2，则返回 0。
     *
     * 示例 1:
     *
     * 输入: [3,6,9,1]
     * 输出: 3
     * 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。
     * 示例 2:
     *
     * 输入: [10]
     * 输出: 0
     *
     * 先基数排序，再求相邻元素最大差值
     * 解释: 数组元素个数小于 2，因此返回 0。
     * @Date 2020-11-26
     * @Param [nums]
     * @return int
     **/
    public int maximumGap(int[] nums) {

        if(nums == null || nums.length <= 1){
            return 0;
        }
        int maxVal = Arrays.stream(nums).max().getAsInt();

        int ep = 1;
        int res [] = new int[nums.length];
        while (maxVal >= ep){
            int [] bucket = new int[10];
            for(int i = 0;i < nums.length;i++){

                int digit = (nums[i] / ep) % 10;
                bucket[digit] ++;
            }

            for(int i = 1;i <=9;i++){
                bucket[i] = bucket[i-1] + bucket[i];
            }

            for(int i = nums.length - 1;i >= 0;i--){
                int digit = (nums[i] / ep) % 10;
                res[bucket[digit] - 1] = nums[i];
                bucket[digit] --;
            }

            System.arraycopy(res, 0, nums, 0, nums.length);
            ep *= 10;
        }

        int max = 0;
        for(int i = 1;i < nums.length;i++){
            max = Math.max(max, nums[i] - nums[i-1]);
        }

        return max;

    }


    /**
     * @author zlx
     * @Description 452. 用最少数量的箭引爆气球  middle
     *
     * 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标。
     *
     * 一支弓箭可以沿着 x 轴从不同点完全垂直地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
     *
     * 给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
     *
     *
     * 示例 1：
     *
     * 输入：points = [[10,16],[2,8],[1,6],[7,12]]
     * 输出：2
     * 解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
     * 示例 2：
     *
     * 输入：points = [[1,2],[3,4],[5,6],[7,8]]
     * 输出：4
     * 示例 3：
     *
     * 输入：points = [[1,2],[2,3],[3,4],[4,5]]
     * 输出：2
     * 示例 4：
     *
     * 输入：points = [[1,2]]
     * 输出：1
     * 示例 5：
     *
     * 输入：points = [[2,3],[2,3]]
     * 输出：1
     *
     * 解题思路： 排序+贪心算法， 核心是找到每次存在交集的最小最右值
     *
     *
     * 提示：
     *
     * 0 <= points.length <= 104
     * points[i].length == 2
     * -231 <= xstart < xend <= 231 - 1
     * @Date 2020-11-23
     * @Param [points]
     * @return int
     **/
    public int findMinArrowShots(int[][] points) {

        if(points.length == 0){
            return 0;
        }

        if(points.length == 1){
            return 1;
        }

        Arrays.sort(points, new Comparator<int[]>() {
            //不能直接用return o1[1]-o2[1] 原因是o1[1] = Integer.MIN_VALUE, o2[1]=Integer.MAX_VALUE,相减操作会int最大最小值
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] < o2[1]){
                    return -1;
                }else if(o1[1] > o2[1]){
                    return 1;
                }else{
                    return 0;
                }
            }
        });

        int last = points[0][1];
        int ans = 1;
        for(int [] ball : points){

            System.out.println(Arrays.toString(ball));
            if(ball[0] > last){
                ans ++;
                last = ball[1];
            }
        }

        return ans;

    }


    public void moveZeroes(int[] nums) {

        if(nums == null || nums.length <= 1){
            return ;
        }
        for(int i = 0;i < nums.length - 1;i++){
            if(nums[i] == 0){
                int j = i+1;
                while (j < nums.length && nums[j] == 0){
                    j++;
                }
                if(j >= nums.length){
                    break;
                }else{
                    nums[i] = nums[j];
                    nums[j] = 0;
                }
            }
        }
    }


    /**
     * @author zlx
     * @Description 1030. 距离顺序排列矩阵单元格 easy
     * 给出 R 行 C 列的矩阵，其中的单元格的整数坐标为 (r, c)，满足 0 <= r < R 且 0 <= c < C。
     *
     * 另外，我们在该矩阵中给出了一个坐标为 (r0, c0) 的单元格。
     *
     * 返回矩阵中的所有单元格的坐标，并按到 (r0, c0) 的距离从最小到最大的顺序排，其中，两单元格(r1, c1) 和 (r2, c2) 之间的距离是曼哈顿距离，|r1 - r2| + |c1 - c2|。（你可以按任何满足此条件的顺序返回答案。）
     *
     *
     *
     * 示例 1：
     *
     * 输入：R = 1, C = 2, r0 = 0, c0 = 0
     * 输出：[[0,0],[0,1]]
     * 解释：从 (r0, c0) 到其他单元格的距离为：[0,1]
     * 示例 2：
     *
     * 输入：R = 2, C = 2, r0 = 0, c0 = 1
     * 输出：[[0,1],[0,0],[1,1],[1,0]]
     * 解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]
     * [[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。
     * 示例 3：
     *
     * 输入：R = 2, C = 3, r0 = 1, c0 = 2
     * 输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
     * 解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]
     * 其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。
     *
     * 更简单的解法： 直接构建int[i][j]， 然后再利用Arrays.sort(res, new Comparator<>)进行排序
     *
     * 提示：
     *
     * 1 <= R <= 100
     * 1 <= C <= 100
     * 0 <= r0 < R
     * 0 <= c0 < C
     * 通过次数19,601提交次数27,969
     * @Date 2020-11-17
     * @Param [R, C, r0, c0]
     * @return int[][]
     **/
    public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {

        int [][] res = new int[R * C][];
        Map<Integer, List<int [][]>> map = new HashMap<>();
        for(int i = 0;i < R;i++){
            for(int j = 0;j < C;j++){
                int d = Math.abs(i - r0) + Math.abs(j - c0);
                List<int [][]> tmp = new ArrayList<>();
                if(map.containsKey(d)){
                    tmp = map.get(d);
                }
                tmp.add(new int [][] {{i,j}});
                map.put(d, tmp);

            }
        }

        List<Integer> list = new ArrayList<>(map.keySet());
        Collections.sort(list);

        int i = 0;
        for(Integer tmp : list){

            List<int [][]> array = map.get(tmp);
            for(int [][] a : array){
                res[i] = a[0];
                i++;
            }
        }
        return res;
    }


    public int[] relativeSortArray(int[] arr1, int[] arr2) {

        Map<Integer, Integer> map = new HashMap<>();
        for(int a : arr1){
            map.put(a, map.getOrDefault(a, 0) + 1);
        }

        int [] res = new int [arr1.length];
        int i = 0;

        for(int a : arr2){
            int times = map.get(a);
            for(int t = 0;t < times;t++){
                res[i] = a;
                i++;
            }
            map.remove(a);
        }

        if(i < res.length) {

            List<Integer> list = new ArrayList<>();
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){

                int times = entry.getValue();
                while (times != 0){
                    list.add(entry.getKey());
                    times--;
                }
            }

            Collections.sort(list);
            for(Integer a : list){

                res[i] = a;
                i++;
            }


        }

        return res;

    }



    /**
     * @author zlx
     * @Description 406. 根据身高重建队列 middle
     * 假设有打乱顺序的一群人站成一个队列。 每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。 编写一个算法来重建这个队列。
     *
     * 注意：
     * 总人数少于1100人。
     *
     * 解题思路：  根据身高i进行升序排列，
     *            hi 排名为ki，排序之后，前0到(i-1)都比他小，因此前面需要空出ki个为止，即这个点在ki+1的位置
     *            hi= hj, 若ki < kj, i一定在j的前面
     *            因此需要对身高h相等的点，进行降序排列
     *
     * 示例
     *
     * 输入:
     * [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
     *
     * 输出:
     * [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
     * @Date 2020-11-16
     * @Param [people]
     * @return int[][]
     **/
    public int[][] reconstructQueue(int[][] people) {

        if(people == null || people.length <= 1){
            return people;
        }

        //根据身高升序排列，身高相等根据排名降序排列
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {

                if(o1[0] != o2[0]){
                    return o1[0] - o2[0];
                }else{
                    return o2[1] - o1[1];
                }

            }
        });
        for(int i = 0;i < people.length;i++){
            System.out.println(Arrays.toString(people[i]));
        }

        int n = people.length;
        int [][] res = new int [n][];
        for(int i = 0;i < n;i++){

            int space = people[i][1] + 1;
            for(int j = 0;j < n;j++){

                if(res[j] == null){
                    space--;
                    if(space == 0){
                        System.out.println("========");
                        res[j] = people[i];
                        break;
                    }
                }
            }
        }

        return res;
    }


    /**
     * @author zlx
     * @Description 973. 最接近原点的 K 个点 middle
     * 我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
     *
     * （这里，平面上两点之间的距离是欧几里德距离。）
     *
     * 你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
     *
     *
     *
     * 示例 1：
     *
     * 输入：points = [[1,3],[-2,2]], K = 1
     * 输出：[[-2,2]]
     * 解释： 
     * (1, 3) 和原点之间的距离为 sqrt(10)，
     * (-2, 2) 和原点之间的距离为 sqrt(8)，
     * 由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
     * 我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。
     * 示例 2：
     *
     * 输入：points = [[3,3],[5,-1],[-2,4]], K = 2
     * 输出：[[3,3],[-2,4]]
     * （答案 [[-2,4],[3,3]] 也会被接受。）
     *
     *
     * 提示：
     *
     * 1 <= K <= points.length <= 10000
     * -10000 < points[i][0] < 10000
     * -10000 < points[i][1] < 10000
     * @Date 2020-11-09
     * @Param [points, K]
     * @return int[][]
     **/
    public int[][] kClosest(int[][] points, int K) {

        Map<Integer, List<Integer>> map = new TreeMap<>();
        for(int i = 0;i < points.length;i++){
            int val = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            List<Integer> tmpVal = new LinkedList<>();
            if(map.containsKey(val)){
                tmpVal = map.get(val);
            }
            tmpVal.add(i);
            map.put(val, tmpVal);
        }


        int [][] res = new int[K][2];
        int index = 0;
        for(Map.Entry<Integer, List<Integer>> entry : map.entrySet()){

            if(index < K){
                List<Integer> vals  = entry.getValue();
                for(Integer val : vals){
                    res[index] = points[val];
                    index++;
                }
            }
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 1356. 根据数字二进制下 1 的数目排序  easy
     * 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
     *
     * 如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
     *
     * 请你返回排序后的数组。
     *
     *
     *
     * 示例 1：
     *
     * 输入：arr = [0,1,2,3,4,5,6,7,8]
     * 输出：[0,1,2,4,8,3,5,6,7]
     * 解释：[0] 是唯一一个有 0 个 1 的数。
     * [1,2,4,8] 都有 1 个 1 。
     * [3,5,6] 有 2 个 1 。
     * [7] 有 3 个 1 。
     * 按照 1 的个数排序得到的结果数组为 [0,1,2,4,8,3,5,6,7]
     * 示例 2：
     *
     * 输入：arr = [1024,512,256,128,64,32,16,8,4,2,1]
     * 输出：[1,2,4,8,16,32,64,128,256,512,1024]
     * 解释：数组中所有整数二进制下都只有 1 个 1 ，所以你需要按照数值大小将它们排序。
     * 示例 3：
     *
     * 输入：arr = [10000,10000]
     * 输出：[10000,10000]
     * 示例 4：
     *
     * 输入：arr = [2,3,5,7,11,13,17,19]
     * 输出：[2,3,5,17,7,11,13,19]
     * 示例 5：
     *
     * 输入：arr = [10,100,1000,10000]
     * 输出：[10,100,10000,1000]
     *
     *
     * 解法一： 暴力破解，分别求出各个数字中1的个数，然后排序
     * 解法二： 规律总结 bits[i] = bits[i >> 1] + (i & 1);
     * 提示：
     *
     * 1 <= arr.length <= 500
     * 0 <= arr[i] <= 10^4
     * @Date 2020-11-06
     * @Param [arr]
     * @return int[]
     **/
    public int[] sortByBits(int[] arr) {


        if(arr.length <= 1){
            return arr;
        }

        int [] bits = new int[10001];
        for(int i = 1;i < bits.length;i++){

            bits[i] = bits[i >> 1] + (i & 1);

            System.out.println(i + ">>2:" + (i>>1) + "===="+i +"&1:" + (i&1) + " bits["+ i +"]:" + bits[i]);
        }
        System.out.println(Arrays.toString(bits));

        List<Integer> res = new ArrayList<>();
        for(int tmp : arr){
            res.add(tmp);
        }

        Collections.sort(res, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                if(bits[o1] != bits[o2]){
                    return bits[o1] - bits[o2];
                }else{
                    return o1 - o2;
                }
            }
        });

        for(int i = 0;i < res.size();i++){

            arr[i] = res.get(i);
        }
        return arr;
    }


    //求解x 二进制中1的个数
    public int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 2;
            x /= 2;
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 57. 插入区间 hard
     * 给出一个无重叠的 ，按照区间起始端点排序的区间列表。
     *
     * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
     *
     *
     *
     * 示例 1：
     *
     * 输入：intervals = [[1,3],[6,9]], newInterval = [2,5]
     * 输出：[[1,5],[6,9]]
     * 示例 2：
     *
     * 输入：intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
     * 输出：[[1,2],[3,10],[12,16]]
     * 解释：这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。
     * @Date 2020-11-04
     * @Param [intervals, newInterval]
     * @return int[][]
     **/
    public int[][] insert(int[][] intervals, int[] newInterval) {


        if(intervals == null || intervals.length == 0){
            return new int [][] {{newInterval[0], newInterval[1]}};
        }
        boolean add = false;
        List<int[][]> res = new ArrayList<>();
        for(int [] interval : intervals){

            if(newInterval[1] < interval[0] && !add){
                res.add(new int[][]{newInterval});
                res.add(new int[][]{interval});
                add = true;
            }
            else if(newInterval[0] > interval[1]){
                res.add(new int[][]{interval});
            }else if(!add){
                newInterval[0] = Math.min(newInterval[0], interval[0]);
                newInterval[1] = Math.max(newInterval[1], interval[1]);
            }else{
                res.add(new int[][]{interval});
            }
        }

        int [][] result = new int[res.size()][2];
        int i = 0;
        for(int[][] tmp : res){
            System.out.println(tmp[0][0] + ",  " +tmp[0][1]);
            result[i][0] = tmp[0][0];
            result[i][1] = tmp[0][1];
            i++;
        }

        if(!add){
            res.add(new int[][]{newInterval});
        }
        return result;
    }

    /**
     * @author zlx
     * @Description 941. 有效的山脉数组 easy
     * 给定一个整数数组 A，如果它是有效的山脉数组就返回 true，否则返回 false。
     *
     * 让我们回顾一下，如果 A 满足下述条件，那么它是一个山脉数组：
     *
     * A.length >= 3
     * 在 0 < i < A.length - 1 条件下，存在 i 使得：
     * A[0] < A[1] < ... A[i-1] < A[i]
     * A[i] > A[i+1] > ... > A[A.length - 1]
     * @Date 2020-11-03
     * @Param [A]
     * @return boolean
     **/
    public boolean validMountainArray(int[] A) {

        if(A == null || A.length < 3){
            return false;
        }
        int maxIndex = 0;
        int max = A[0];
        for(int i = 1;i < A.length;i++){

            if(A[i] > max){
                maxIndex = i;
                max = A[i];
            }else if(A[i] == max){
                return false;
            }
        }

        if(maxIndex == 0 || maxIndex == A.length - 1){
            return false;
        }

        for(int i = 1;i < maxIndex;i++){

            if(A[i-1] >= A[i]){
                return false;
            }
        }

        for(int i = maxIndex + 1;i < A.length - 1;i++){
            if(A[i] <= A[i+1]){
                return false;
            }
        }
        return true;
    }


    public int[] intersection(int[] nums1, int[] nums2) {

        Set<Integer> set = new HashSet<>();
        for(int num : nums1){
            set.add(num);
        }

        Set<Integer> res = new HashSet<>();
        for(int num : nums2){
            if(set.contains(num)){
                res.add(num);
            }
        }

        int [] r = new int[set.size()];
        int i = 0;
        for(Integer s : res){
            r[i] = s;
            i++;
        }

        return r;
    }


    /**
     * @author zlx easy
     * @Description 给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。
     *
     * 如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：arr = [1,2,2,1,1,3]
     * 输出：true
     * 解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。
     * 示例 2：
     *
     * 输入：arr = [1,2]
     * 输出：false
     * 示例 3：
     *
     * 输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
     * 输出：true
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/unique-number-of-occurrences
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @Date 2020-10-28
     * @Param [arr]
     * @return boolean
     **/
    public boolean uniqueOccurrences(int[] arr) {

        if(arr == null || arr.length <= 1) {
            return true;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for(int tmp : arr){

            if(map.containsKey(tmp)){
                map.put(tmp, map.get(tmp) + 1);
            }else{
                map.put(tmp, 1);
            }
        }

        HashSet<Integer> hashSet = new HashSet<>();
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            hashSet.add(entry.getValue());
        }
        return map.size() == hashSet.size();
    }



    public int[] smallerNumbersThanCurrent(int[] nums) {

        int[] res = new int[nums.length];
        for(int i = 0;i < nums.length;i++){

            int counts = 0;
            for(int j = 0;j < nums.length;j++){

                if(i!= j && nums[j] < nums[i]){
                    counts ++;
                }
            }
            res[i] = counts;
        }
        return res;
    }

    /**
     * @author zlx
     * @Description 1002. 查找常用字符 easy
     * 给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现 3 次，但不是 4 次，则需要在最终答案中包含该字符 3 次。
     *
     * 你可以按任意顺序返回答案。
     *
     *
     *
     * 示例 1：
     *
     * 输入：["bella","label","roller"]
     * 输出：["e","l","l"]
     * 示例 2：
     *
     * 输入：["cool","lock","cook"]
     * 输出：["c","o"]
     *
     *
     * 提示：
     *
     * 1 <= A.length <= 100
     * 1 <= A[i].length <= 100
     * A[i][j] 是小写字母
     * @Date 2020-10-14
     * @Param [A]
     * @return java.util.List<java.lang.String>
     **/
    public List<String> commonChars(String[] A) {

        List<String> res = new ArrayList<>();
        if(A == null || A.length <= 0){
            return res;
        }

        int [] minFreq = new int[26];
        Arrays.fill(minFreq, Integer.MAX_VALUE);
        for(String a: A){

            int [] freq = new int[26];
            for(int i = 0;i < a.length();i++){
                freq[a.charAt(i) - 'a'] ++;
            }

            for(int i = 0;i < freq.length;i++){
                minFreq[i] = Math.min(freq[i], minFreq[i]);
            }
        }



        for(int i = 0;i < 26;i++){

            for(int j = 0;j < minFreq[i];j++){
                char tmp = (char) (i + 'a');
                res.add(String.valueOf(tmp));
            }
        }
        return res;
    }


    /**
     * @author zlx
     * @Description  1535. 找出数组游戏的赢家 middle
     * 给你一个由 不同 整数组成的整数数组 arr 和一个整数 k 。
     *
     * 每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家 。
     *
     * 返回赢得比赛的整数。
     *
     * 题目数据 保证 游戏存在赢家。
     *
     *
     *
     * 示例 1：
     *
     * 输入：arr = [2,1,3,5,4,6,7], k = 2
     * 输出：5
     * 解释：一起看一下本场游戏每回合的情况：
     *
     * 因此将进行 4 回合比赛，其中 5 是赢家，因为它连胜 2 回合。
     * 示例 2：
     *
     * 输入：arr = [3,2,1], k = 10
     * 输出：3
     * 解释：3 将会在前 10 个回合中连续获胜。
     * 示例 3：
     *
     * 输入：arr = [1,9,8,2,3,7,6,4,5], k = 7
     * 输出：9
     * 示例 4：
     *
     * 输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
     * 输出：99
     *
     *
     * 提示：
     *
     * 2 <= arr.length <= 10^5
     * 1 <= arr[i] <= 10^6
     * arr 所含的整数 各不相同 。
     * 1 <= k <= 10^9
     *
     * 解题思路：当k=1， 一次就能分出胜负， res = Math.max(arr[0], arr[1])
     *          当k>1时， 每次都是胜出的值prev 和数组中下一个元arr[i]素进行对比，
     *          当prev > arr[i], 胜出次数+1, 并将胜出次数和k比较，times==k, 胜出值为prev；
     *          否则，更新胜出值prev=arr[i], times=1;
     *          当遍历数组之后没有结果，则返回数组的最大值
     *
     *
     * @Date 2020-10-12
     * @Param [arr, k]
     * @return int
     **/
    public int getWinner(int[] arr, int k) {

        if(arr == null || arr.length <= 0 || k == 0){
            return 0;
        }

        int prev = Math.max(arr[0], arr[1]);
        if(k == 1){
            return prev;
        }

        int times = 1;
        int maxInArray = prev;

        for(int i = 2;i < arr.length;i++){
            int second = arr[i];
            if(prev > second){
                times++;

                if(times == k){
                    return prev;
                }
            }else{
                prev = second;
                times = 1;
            }
            maxInArray = Math.max(maxInArray, second);
        }
        return maxInArray;

    }

    /**
     * @author zlx
     * @Description 暴力解法：用Queue模拟整个过程，会超出时间限制；
     * @Date 2020-10-12
     * @Param [arr, k]
     * @return int
     **/
    public int getWinnerII(int[] arr, int k) {

        if(arr == null || arr.length <= 0 || k == 0){
            return 0;
        }

        Queue<Integer> queue = new LinkedList<>();
        for(int i : arr){
            queue.add(i);
        }

        int res = queue.peek();
        int tmp = 0;
        while (tmp < k){

            int second = ((LinkedList<Integer>) queue).get(1);
            if(res < second){
                ((LinkedList<Integer>) queue).addLast(res);
                ((LinkedList<Integer>) queue).removeFirst();
                res = queue.peek();
                tmp = 1;
            }else{
                ((LinkedList<Integer>) queue).remove(1);
                ((LinkedList<Integer>) queue).addLast(second);
                tmp ++;
            }
        }

        return res;
    }


    /**
     * @author zlx
     * @Description 347. 前 K 个高频元素  middle
     * 给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
     *
     *
     *
     * 示例 1:
     *
     * 输入: nums = [1,1,1,2,2,3], k = 2
     * 输出: [1,2]
     * 示例 2:
     *
     * 输入: nums = [1], k = 1
     * 输出: [1]
     *
     * 解题思路：首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」。找出原数组的前 kk 个高频元素，就相当于找出「出现次数数组」的前 kk 大的值。
     *
     * 最简单的做法是给「出现次数数组」排序。但由于可能有 O(N)O(N) 个不同的出现次数（其中 NN 为原数组长度），故总的算法复杂度会达到 O(N\log N)O(NlogN)，不满足题目的要求。
     *
     * 在这里，我们可以利用堆的思想：建立一个小顶堆，然后遍历「出现次数数组」：
     *
     * 如果堆的元素个数小于 kk，就可以直接插入堆中。
     * 如果堆的元素个数等于 kk，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有 kk 个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。
     * 遍历完成后，堆中的元素就代表了「出现次数数组」中前 kk 大的值。
     *

     *
     * @Date 2020-09-07
     * @Param [nums, k]
     * @return int[]
     *
     **/
    public int[] topKFrequent(int[] nums, int k) {

        if(nums == null || nums.length == 0 || k > nums.length){
            return null;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(Integer i : nums){
            Integer tmp = 0;
            if(map.containsKey(i)){
                tmp = map.get(i);
            }
            tmp++;
            map.put(i, tmp);
        }
        int [] res = new int[k];

        PriorityQueue<int []> priorityQueue = new PriorityQueue<int []>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        for(Map.Entry<Integer, Integer> entry : map.entrySet()){

            int num = entry.getKey();
            int count = entry.getValue();

            if(priorityQueue.size() == k){

                if(priorityQueue.peek()[0] < count){
                    priorityQueue.poll();
                    priorityQueue.offer(new int [] {count, num});
                }
            }else{
                priorityQueue.offer(new int [] {count, num});
            }
        }

        for(int i = k-1;i >=0;i--){
            res[i] = priorityQueue.poll()[1];
        }
        return res;
    }

    /**
     * @author zlx
     * @Description 491. 递增子序列
     * 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
     *
     * 示例:
     *
     * 输入: [4, 6, 7, 7]
     * 输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]
     * 说明:
     *
     * 给定数组的长度不会超过15。
     * 数组中的整数范围是 [-100,100]。
     * 给定数组中可能包含重复数字，相等的数字应该被视为递增的一种情况。
     *
     *
     *
     * 解题思路： 递归+减枝
     * @Date 2020-08-25
     * @Param [nums]
     * @return java.util.List<java.util.List<java.lang.Integer>>
     *
     *
     *
     **/
    public List<List<Integer>> findSubsequences(int[] nums) {

        res = new ArrayList<>();
        if(nums == null || nums.length < 2){
            return null;
        }

//        for(int i = 0;i < nums.length - 1;i++){
////            for(int j = i+1;j < nums.length;j++){
////                List<Integer> tmp = new ArrayList<>();
////                tmp.add(nums[i]);
////                findSubsequences(nums, j, tmp);
////            }
////        }
        dfsFindSubsequence(0, Integer.MIN_VALUE, nums);
        return res;

    }


    //List<List<Integer>> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();

    public void dfsFindSubsequence(int cur, int last, int[] nums){

        if (cur == nums.length) {
            if (temp.size() >= 2) {
                res.add(new ArrayList<Integer>(temp));
            }
            return;
        }
        if (nums[cur] >= last) {
            temp.add(nums[cur]);
            dfsFindSubsequence(cur + 1, nums[cur], nums);
            temp.remove(temp.size() - 1);
        }
        if (nums[cur] != last) {
            dfsFindSubsequence(cur + 1, last, nums);
        }

    }




    public void findSubsequences(int [] nums, int start, List<Integer> increaseList){

        if(increaseList.size() >= 2){
            List<Integer> tmp = new ArrayList<>(increaseList);

            if(!res.contains(tmp))
                res.add(tmp);
        }

        if(start > nums.length){
            return ;
        }


        if (start < nums.length && nums[start] >= increaseList.get(increaseList.size() - 1)) {
            increaseList.add(nums[start]);
            findSubsequences(nums, start + 1, increaseList);
        }
        increaseList.remove(increaseList.size() - 1);

    }


    public static final int TARGER = 24;
    public static final int ADD = 0, MULTIPLY = 1, SUBTRACT = 2, DIVIDE = 3;
    public static final double EPLISON = 1e-10;
    /**
     * @author zlx
     * @Description 679. 24 点游戏 hard 回溯法进行求解
     * 你有 4 张写有 1 到 9 数字的牌。你需要判断是否能通过 *，/，+，-，(，) 的运算得到 24。
     *
     * 示例 1:
     *
     * 输入: [4, 1, 8, 7]
     * 输出: True
     * 解释: (8-4) * (7-1) = 24
     * 示例 2:
     *
     * 输入: [1, 2, 1, 2]
     * 输出: False
     * 注意:
     *
     * 除法运算符 / 表示实数除法，而不是整数除法。例如 4 / (1 - 2/3) = 12 。
     * 每个运算符对两个数进行运算。特别是我们不能用 - 作为一元运算符。例如，[1, 1, 1, 1] 作为输入时，表达式 -1 - 1 - 1 - 1 是不允许的。
     * 你不能将数字连接在一起。例如，输入为 [1, 2, 1, 2] 时，不能写成 12 + 12 。
     * @Date 2020-08-24
     *
     * 解题思路： 4个数字，有3个操作符； 利用回溯法，
     *  第一次从4个数字选2个，4*3个选择， 操作符4个选择，计算结果再放回去
     *  第二次从3个数组选2个，3*2个选择，操作符有4个选择，
     *  第三是2个数字中选2个，有2*1个选择，操作符有4个选择，计算结果和24比较，由于/表示实数除法，因此要精度考虑小数点后6为0.000001，
     * @Param [nums]
     * @return boolean
     **/
    public boolean judgePoint24(int[] nums) {

        List<Double> numList = new ArrayList<>();
        for(int i : nums){
            numList.add((double) i);
        }
        return solve(numList);

    }


    public boolean solve(List<Double> input){

        if(input.size() == 0){
            return false;
        }

        if(input.size() == 1){
            return Math.abs(input.get(0) - TARGER) < EPLISON;
        }

        int size = input.size();
        for(int i = 0;i < size;i++){
            for(int j = 0;j < size;j++){
                if(i != j){

                    List<Double> newList = new ArrayList<>();
                    for(int k = 0; k< size;k++){
                        if(k != i && k != j) {
                            newList.add(input.get(k));
                        }
                    }
                    for(int k = 0;k < 4;k++) {
                        if (k < 2 && i > j) {
                            continue;
                        }
                        if(k == ADD){
                            newList.add(input.get(i) + input.get(j));
                        }else if(k == MULTIPLY){
                            newList.add(input.get(i) * input.get(j));
                        }else if(k == SUBTRACT){
                            newList.add(input.get(i) - input.get(j));
                        }else if(k == DIVIDE){
                            if(Math.abs(input.get(j)) < EPLISON){
                                continue;
                            }else{
                                newList.add(input.get(i) / input.get(j));
                            }
                        }
                        if(solve(newList)){
                            return true;
                        }
                        newList.remove(newList.size() - 1);
                    }
                }
            }
        }
        return false;
    }

    /**
     * @author zlx
     * @Description 336. 回文对   hard
     *
     * 给定一组 互不相同 的单词， 找出所有不同 的索引对(i, j)，使得列表中的两个单词， words[i] + words[j] ，可拼接成回文串。
     *
     *
     *
     * 示例 1：
     *
     * 输入：["abcd","dcba","lls","s","sssll"]
     * 输出：[[0,1],[1,0],[3,2],[2,4]]
     * 解释：可拼接成的回文串为 ["dcbaabcd","abcddcba","slls","llssssll"]
     * 示例 2：
     *
     * 输入：["bat","tab","cat"]
     * 输出：[[0,1],[1,0]]
     * 解释：可拼接成的回文串为 ["battab","tabbat"]
     * @Date 2020-08-06
     * @Param [words]
     *
     *
     * 解题思路：暴力法, 两两拼接，判读是否为会问串，但是会超时
     *
     * @return java.util.List<java.util.List<java.lang.Integer>>
     **/
    public List<List<Integer>> palindromePairs(String[] words) {

        if(words == null || words.length <= 1){
            return null;
        }

        List<List<Integer>> res = new ArrayList<>();

        for(int i = 0;i < words.length;i++){
            for(int j = 0;j < words.length;j++){

                if(j == i){
                    continue;
                }
                String waitJudge = words[i] + words[j];
                if(judeIsPalindrome(waitJudge)){
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(i);
                    tmp.add(j);
                    res.add(tmp);
                }
            }
        }
        return res;
    }


    public boolean judeIsPalindrome(String waitJude){

        if(waitJude == null || waitJude.length() <= 1){
            return true;
        }

        int i = 0, j = waitJude.length() - 1;
        while (i < j){

            if(waitJude.charAt(i) != waitJude.charAt(j)){
                return false;
            }
            i++;
            j--;
        }
        return true;

    }


    class Node {
        int[] ch = new int[26];
        int flag;

        public Node() {
            flag = -1;
        }
    }

    List<Node> tree = new ArrayList<Node>();

    //解法二
    /**
     * 方法一：枚举前缀和后缀
     * 思路及算法
     **/
    public List<List<Integer>> palindromePairsII(String[] words) {
        tree.add(new Node());
        int n = words.length;
        for (int i = 0; i < n; i++) {
            insert(words[i], i);
        }
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < n; i++) {
            int m = words[i].length();
            for (int j = 0; j <= m; j++) {
                if (isPalindrome(words[i], j, m - 1)) {
                    int leftId = findWord(words[i], 0, j - 1);
                    if (leftId != -1 && leftId != i) {
                        ret.add(Arrays.asList(i, leftId));
                    }
                }
                if (j != 0 && isPalindrome(words[i], 0, j - 1)) {
                    int rightId = findWord(words[i], j, m - 1);
                    if (rightId != -1 && rightId != i) {
                        ret.add(Arrays.asList(rightId, i));
                    }
                }
            }
        }
        return ret;
    }

    public void insert(String s, int id) {
        int len = s.length(), add = 0;
        for (int i = 0; i < len; i++) {
            int x = s.charAt(i) - 'a';
            if (tree.get(add).ch[x] == 0) {
                tree.add(new Node());
                tree.get(add).ch[x] = tree.size() - 1;
            }
            add = tree.get(add).ch[x];
        }
        tree.get(add).flag = id;
    }

    public boolean isPalindrome(String s, int left, int right) {
        int len = right - left + 1;
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(left + i) != s.charAt(right - i)) {
                return false;
            }
        }
        return true;
    }

    public int findWord(String s, int left, int right) {
        int add = 0;
        for (int i = right; i >= left; i--) {
            int x = s.charAt(i) - 'a';
            if (tree.get(add).ch[x] == 0) {
                return -1;
            }
            add = tree.get(add).ch[x];
        }
        return tree.get(add).flag;
    }



    public int findMagicIndex(int[] nums) {

        if(nums == null || nums.length <= 0){
            return -1;
        }

        for(int i =0;i < nums.length;i++){

            if(nums[i] == i){
                return i;
            }
        }
        return -1;
    }


    /**
     * @author zlx
     * @Description 343. 整数拆分
     * 给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
     *
     * 示例 1:
     *
     * 输入: 2
     * 输出: 1
     * 解释: 2 = 1 + 1, 1 × 1 = 1。
     * 示例 2:
     *
     * 输入: 10
     * 输出: 36
     * 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
     * 说明: 你可以假设 n 不小于 2 且不大于 58。
     *
     * 解题思路： 基于动态规划求解， n = a+b; res[i] 表示n=i 时的最大乘积， i = a + (i - a)
     * 因此 res[i] = max(res[a] * res[i-a])
     * @Date 2020-07-30
     * @Param [n]
     * @return int
     **/
    public int integerBreak(int n) {

        if(n == 2){
            return 1;
        }
        if(n == 3){
            return 2;
        }

        int [] res = new int[n+1];
        res[1] = 1;
        res[2] = 2;
        res[3] = 3;

        for(int i = 4;i <= n;i++){
            int tmp = Integer.MIN_VALUE;
            int bound = i /2;
            for(int j = 1; j <= bound;j++){
                tmp = Integer.max(tmp, res[j] * res[i - j]);
            }
            res[i] = tmp;

        }

        return res[n];
    }


    /**
     * @author zlx
     * @Description 79. 单词搜索 middle
     * 给定一个二维网格和一个单词，找出该单词是否存在于网格中。
     *
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     *
     *
     *
     * 示例:
     *
     * board =
     * [
     *   ['A','B','C','E'],
     *   ['S','F','C','S'],
     *   ['A','D','E','E']
     * ]
     *
     * 给定 word = "ABCCED", 返回 true
     * 给定 word = "SEE", 返回 true
     * 给定 word = "ABCB", 返回 false
     *
     *
     * 提示：
     *
     * board 和 word 中只包含大写和小写英文字母。
     * 1 <= board.length <= 200
     * 1 <= board[i].length <= 200
     * 1 <= word.length <= 10^3
     * @Date 2020-07-29
     * @Param [board, word]
     * @return boolean
     **/
    public boolean exist(char[][] board, String word) {

        if(board == null || board.length <= 0 || word == null || word.length() <= 0){
            return false;
        }

        int [][] directions = {{0,1}, {1,0}, {0,-1},{-1,0}};

        for(int i = 0;i < board.length;i++){
            for(int j = 0;j < board[0].length;j++){

                boolean [][] flag = new boolean [board.length][board[0].length];
                if(dfs(board, directions, i, j, word, 0, flag)){
                    return true;
                }

            }
        }
        return false;

    }

    public boolean dfs(char [][] board, int [][] directions, int x, int y, String word, int wordIndex, boolean flag[][]){

        if(wordIndex == word.length() - 1){
            return board[x][y] == word.charAt(wordIndex);
        }

        if(board[x][y] == word.charAt(wordIndex)) {
            flag[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int tmpX = x + directions[i][0];
                int tmpY = y + directions[i][1];
                if (tmpX >= 0 && tmpX < board.length
                        && tmpY >= 0 && tmpY < board[0].length
                        && !flag[tmpX][tmpY]) {

                    if(dfs(board, directions, tmpX, tmpY, word, wordIndex + 1, flag)){
                        return true;
                    }
                }
            }
            flag[x][y] = false;
        }
        return false;
    }

    
    //dfs方法2
    public boolean existII(char[][] board, String word) {

        if(board == null || board.length <= 0 || word == null || word.length() <= 0){
            return false;
        }
        for(int i = 0;i < board.length;i++){
            for(int j = 0;j < board[0].length;j++){
                flag = new boolean [board.length][board[0].length];
                if(dfsII(board, i, j, word, 0)){
                    return true;
                }
            }
        }
        return false;

    }

    public static int [][] directions = {{0,1}, {1,0}, {0,-1},{-1,0}};
    public static boolean [][] flag;


    public boolean dfsII(char [][] board, int x, int y, String word, int wordIndex){

        if(wordIndex == word.length() - 1){
            return board[x][y] == word.charAt(wordIndex);
        }

        if(board[x][y] == word.charAt(wordIndex)) {
            flag[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int tmpX = x + directions[i][0];
                int tmpY = y + directions[i][1];
                if (tmpX >= 0 && tmpX < board.length
                        && tmpY >= 0 && tmpY < board[0].length
                        && !flag[tmpX][tmpY]) {
                    if(dfsII(board, tmpX, tmpY, word, wordIndex + 1)){
                        return true;
                    }
                }
            }
            flag[x][y] = false;
        }
        return false;
    }

    /**
     * @author zlx
     * @Description 35. 搜索插入位置   easy
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     *
     * 你可以假设数组中无重复元素。
     *
     * 示例 1:
     *
     * 输入: [1,3,5,6], 5
     * 输出: 2
     * 示例 2:
     *
     * 输入: [1,3,5,6], 2
     * 输出: 1
     * 示例 3:
     *
     * 输入: [1,3,5,6], 7
     * 输出: 4
     * 示例 4:
     *
     * 输入: [1,3,5,6], 0
     * 输出: 0
     * @Date 2020-07-20
     * @Param [nums, target]
     * @return int
     **/
    public int searchInsert(int[] nums, int target) {

        if(nums == null || nums.length <=0){
            return 0;
        }
        return binarySearch(nums, target, 0, nums.length - 1);
    }

    public int binarySearch(int[] nums, int target, int start, int end){

        if(start > end){
            return start;
        }
        int middle = (start + end) / 2;
        if(nums[middle] == target){
            return middle;
        }else if(nums[middle] > target){
            return binarySearch(nums, target, start, middle - 1);
        }else{
            return binarySearch(nums, target, middle + 1, end);
        }

    }
    

    /**
     * @author zlx
     * @Description 670. 最大交换 middle
     * 给定一个非负整数，你至多可以交换一次数字中的任意两位。返回你能得到的最大值。
     *
     * 示例 1 :
     *
     * 输入: 2736
     * 输出: 7236
     * 解释: 交换数字2和数字7。
     * 示例 2 :
     *
     * 输入: 9973
     * 输出: 9973
     * 解释: 不需要交换。
     * 注意:
     *
     * 给定数字的范围是 [0, 108]
     * @Date 2020-07-15
     * @Param [num]
     * @return int
     **/
    public int maximumSwap(int num) {

        char[] digits = Integer.toString(num).toCharArray();

        //buckets[i] = j 表示数字j在num中的第i个位置(多个相同的j，存最后一个出现的位置)
        int[] buckets = new int[10];
        for (int i = 0; i < digits.length; i++) {
            buckets[digits[i] - '0'] = i;
        }

        for (int i = 0; i < digits.length; i++) {
            //查找到第一个比digit[i]大的值，交换
            for (int k = 9; k > digits[i] - '0'; k--) {
                if (buckets[k] > i) {
                    char tmp = digits[i];
                    digits[i] = digits[buckets[k]];
                    digits[buckets[k]] = tmp;
                    return Integer.valueOf(new String(digits));
                }
            }
        }

        return num;

    }


    public int[] intersect(int[] nums1, int[] nums2) {

        if(nums1 == null || nums2 == null || nums1.length <= 0 || nums2.length <= 0){
            return new int[0];
        }

        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0;i < nums1.length;i++){

            if(map.containsKey(nums1[i])){
                map.put(nums1[i], map.get(nums1[i]) + 1);
            }else{
                map.put(nums1[i], 1);
            }
        }


        List<Integer> res = new ArrayList<>();
        for(int i = 0;i < nums2.length;i++){

            if(map.containsKey(nums2[i]) && map.get(nums2[i]) >= 0){

                res.add(nums2[i]);
                map.put(nums2[i], map.get(nums2[i]) - 1);
            }
        }


        int [] r = new int[res.size()];
        for(int i = 0;i < res.size();i++){
            r[i] = res.get(i);
        }

        return r;
    }


    /**
     * @author zlx
     * @Description
     * 面试题 16.11. 跳水板
     * 你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
     *
     * 返回的长度需要从小到大排列。
     *
     * 示例：
     *
     * 输入：
     * shorter = 1
     * longer = 2
     * k = 3
     * 输出： {3,4,5,6}
     * 提示：
     *
     * 0 < shorter <= longer
     * 0 <= k <= 100000
     *
     *
     * 解题关键： k= a* shorter + (k- a) * longer 数组长度是k+1
     * @Date 2020-07-08
     * @Param [shorter, longer, k]
     * @return int[]
     **/
    public int[] divingBoard(int shorter, int longer, int k) {

        if (k == 0) {
            return new int[0];
        }
        if (shorter == longer) {
            return new int[]{shorter * k};
        }
        int[] lengths = new int[k + 1];
        for (int i = 0; i <= k; i++) {
            lengths[i] = shorter * (k - i) + longer * i;
        }
        return lengths;
        
        
        //此方法会超时
        
//        if(k <= 0){
//            return new int[0];
//        }
//        List<Integer> res = new ArrayList<>();
//        for(int i = k;i >= 0;i--){
//            int tmp = i * shorter + (k - i) * longer;
//            //System.out.println("tmp=====" + tmp);
//            if(!res.contains(tmp)){
//                res.add(tmp);
//            }
//
//        }
//        int [] r= new int[res.size()];
//        int index = 0;
//        for(Integer i : res){
//            //System.out.println(i);
//            r[index] = i;
//            index++;
//        }
//        return r;
    }


    /**
     *
     * 718. 最长重复子数组 middle
     * 给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
     *
     *
     *
     * 示例：
     *
     * 输入：
     * A: [1,2,3,2,1]
     * B: [3,2,1,4,7]
     * 输出：3
     * 解释：
     * 长度最长的公共子数组是 [3, 2, 1] 。
     *
     * 解题思路：本质上是最长公共子串问题，而不是最长公共子序列问题
     * @param A
     * @param B
     * @return
     */
    public int findLength(int[] A, int[] B) {

        if(A == null || B == null || A.length <= 0 || B.length <= 0){
            return 0;
        }

        int result = Integer.MIN_VALUE;
        int [][] res = new int[A.length + 1][B.length + 1];

        for(int i = 1;i <= A.length;i++){

            for(int j = 1;j <= B.length;j++){

                if(A[i - 1] == B[j - 1]){
                    res[i][j] = res[i-1][j-1] + 1;
                    result = Math.max(result, res[i][j]);
                }else{
                    res[i][j] = 0;
                }
            }
        }
        return result;
    }


    /**
     * 1300. 转变数组后最接近目标值的数组和
     * 给你一个整数数组 arr 和一个目标值 target ，请你返回一个整数 value ，使得将数组中所有大于 value 的值变成 value 后，数组的和最接近  target （最接近表示两者之差的绝对值最小）。
     *
     * 如果有多种使得和最接近 target 的方案，请你返回这些整数中的最小值。
     *
     * 请注意，答案不一定是 arr 中的数字。
     *
     *
     *
     * 示例 1：
     *
     * 输入：arr = [4,9,3], target = 10
     * 输出：3
     * 解释：当选择 value 为 3 时，数组会变成 [3, 3, 3]，和为 9 ，这是最接近 target 的方案。
     * 示例 2：
     *
     * 输入：arr = [2,3,5], target = 10
     * 输出：5
     * 示例 3：
     *
     * 输入：arr = [60864,25176,27249,21296,20204], target = 56803
     * 输出：11361
     * @param arr
     * @param target
     * @return
     */
    public int findBestValue(int[] arr, int target) {
        if(arr == null || arr.length <= 0){
            return 0;
        }
        int mean = target/ arr.length;
        Arrays.sort(arr);
        int i = 0;
        for(i = 0;i < arr.length;i++){

            if(arr[i] <= mean){
                target -= arr[i];
            }else{
                break;
            }
        }

        Integer res = Integer.MAX_VALUE;
        for(int j = mean;j < arr[arr.length - 1];j++){

            int tmp = Math.abs(target - j * (arr.length - i));
            if(tmp >= res){
                return  j - 1;
            }else {
                res = tmp;
            }
            if(j == arr[i]){
                target -= arr[i];
                i++;
            }
        }
        return arr[arr.length - 1];

    }



    /**
     * @author zlx
     * @desc 990. 等式方程的可满足性
     * 给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。
     *
     * 只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。
     *
     *
     *
     * 示例 1：
     *
     * 输入：["a==b","b!=a"]
     * 输出：false
     * 解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
     * 示例 2：
     *
     * 输出：["b==a","a==b"]
     * 输入：true
     * 解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
     * 示例 3：
     *
     * 输入：["a==b","b==c","a==c"]
     * 输出：true
     * 示例 4：
     *
     * 输入：["a==b","b!=c","c==a"]
     * 输出：false
     * 示例 5：
     *
     * 输入：["c==c","b==d","x!=z"]
     * 输出：true
     *
     *
     * 提示：
     *
     * 1 <= equations.length <= 500
     * equations[i].length == 4
     * equations[i][0] 和 equations[i][3] 是小写字母
     * equations[i][1] 要么是 '='，要么是 '!'
     * equations[i][2] 是 '='
     *
     *
     *
     * 解题思路：并查集 数据结构，
     * @date  2020-06-08
     * @param equations
     * @return boolean
     **/
    public boolean equationsPossible(String[] equations) {

        if(equations == null || equations.length <= 1){
            return true;
        }

        int [] parent = new int [26];
        for(int i = 0;i < 26;i++){
            parent[i] = i;
        }

        for(String equation : equations){

            if(equation.charAt(1) == '='){
                int index1 = equation.charAt(0) - 'a';
                int index2 = equation.charAt(3) - 'a';
                union(parent, index1, index2);
            }
        }

        for(String equation : equations){

            if(equation.charAt(1) == '!'){
                int index1 = equation.charAt(0) - 'a';
                int index2 = equation.charAt(3) - 'a';
                if(findParent(parent, index1) == findParent(parent, index2)){
                    return false;
                }
            }
        }

        return true;
    }

    public void union(int [] parent, int index1, int index2){
        parent[findParent(parent, index1)] = parent[findParent(parent, index2)];
    }

    public int findParent(int [] parent, int index){

        while (parent[index] != index){
            parent[index] = parent[parent[index]];
            index = parent[index];
        }
        return index;
    }

    /**
     * @author zlx
     * @desc 面试题29. 顺时针打印矩阵
     * 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
     *
     *
     *
     * 示例 1：
     *
     * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
     * 输出：[1,2,3,6,9,8,7,4,5]
     * 示例 2：
     *
     * 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
     * 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
     *
     *
     * 限制：
     *
     * 0 <= matrix.length <= 100
     * 0 <= matrix[i].length <= 100
     * @date  2020-06-08
     * @param matrix
     * @return int[]
     **/
    public int[] spiralOrder(int[][] matrix) {

        if(matrix == null || matrix.length == 0){
            return new int[0];
        }

        int row = matrix.length;
        int col = matrix[0].length;

        int [] res = new int [row * col];

//        if(row == 1){
//            return matrix[0];
//        }
//
//        if(col == 1){
//            for(int i = 0; i < row;i++){
//                res[i] = matrix[i][0];
//            }
//            return res;
//        }

        int index = 0;
        int times = (row + 1) / 2;
        for(int i = 0;i < times;i++){
            int startX = i;
            int startY = i;
            for(int j = startY; j <= (col - 1 - startY)  && index < res.length;j++){
                res[index] = matrix[startX][j];
                index ++;
            }

            for(int tmpX = startX + 1; tmpX <= (row - 1 - startX)  && index < res.length;tmpX++){
                res[index] = matrix[tmpX][col- 1 - startY];
                index ++;
            }

            for(int j = (col - startY - 2);j >= startY && index < res.length;j--){

                res[index] = matrix[row - 1 - startX][j];
                index ++;
            }

            for(int tmpX = (row - 2 - startX); tmpX > startX  && index < res.length;tmpX --){
                res[index] = matrix[tmpX][startY];
                index++;
            }
        }
        return  res;
    }

    
    /**
     * @author zlx
     * @desc 238. 除自身以外数组的乘积   middle
     * 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
     *
     *
     *
     * 示例:
     *
     * 输入: [1,2,3,4]
     * 输出: [24,12,8,6]
     *
     *
     * 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
     *
     * 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
     *
     * 进阶：
     * 你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
     *
     *
     * 基础班解题思路： L[i]表示nums[i] 左边的乘积； R[i]表示nums[i] 右边的乘积
     *   res[i] = L[i] * R[i]
     * @date  2020-06-04
     * @param nums
     * @return int[]
     **/
    public int[] productExceptSelf(int[] nums) {

        if(nums == null || nums.length <= 0){
            return nums;
        }

        int len = nums.length;
        int [] L = new int[len];
        int [] R = new int[len];

        L[0] = 1;
        R[len - 1] = 1;
        for(int i = 1;i < len;i++){
            L[i] = L[i- 1] * nums[i - 1];
        }
        System.out.println("=L====="+ Arrays.toString(L));

        for(int j = len - 2;j >=0;j--){
            R[j] = R[j+1] * nums[j + 1];
        }

        System.out.println("=R====="+ Arrays.toString(R));
        int [] res = new int[len];
        for(int i = 0;i < len;i++){
            res[i] = L[i] * R[i];
        }
        return res;
    }

    /**
     * @author zlx
     * @des 4. 寻找两个正序数组的中位数  hard
     * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
     *
     * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
     *
     * 你可以假设 nums1 和 nums2 不会同时为空。
     *
     *
     *
     * 示例 1:
     *
     * nums1 = [1, 3]
     * nums2 = [2]
     *
     * 则中位数是 2.0
     * 示例 2:
     *
     * nums1 = [1, 2]
     * nums2 = [3, 4]
     *
     * 则中位数是 (2 + 3)/2 = 2.5
     *
     * 官方由于时间复杂度要求是O(m+n), 使用二分查找   m+n 是基数， 中位数下标是（m+n）/2 , m+n 是偶数， 中位数下表是：（m+n）/2, (m+n)/2 + 1
     *
     * 自己方法： 查找中间值
     * @date  2020-05-31
     * @param nums1
     * @param nums2
     * @return double
     **/
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        if((nums1 == null && nums2 == null) || (nums1.length == 0 && nums2.length == 0)){
            return 0;
        }

        double res  = 0.0;
        int m = nums1.length;
        int n = nums2.length;
        int middle = (m + n) / 2;
        int startA = 0, startB =0;
        int mid = 0;
        while (mid < middle){

            if(startA < m && startB < n){
                int a = nums1[startA];
                int b = nums2[startB];
                if(a < b){
                    startA++;
                    mid++;
                }else{
                    startB++;
                    mid++;
                }
            }else if(startB < n){
                startB++;
                mid++;
            }else if(startA < m){
                startA ++;
                mid++;
            }
        }

        System.out.println("startA====" + startA);
        System.out.println("startB is:======" + startB);


        int leftA = Integer.MIN_VALUE, leftB = Integer.MIN_VALUE;
        int rightA = Integer.MAX_VALUE, rightB = Integer.MAX_VALUE;

        if(startA - 1 >= 0){
            leftA = nums1[startA - 1];
        }

        if(startB - 1 >= 0){
            leftB = nums2[startB - 1];
        }

        int maxLeft = Math.max(leftA, leftB);

        if(startA < m) {
            rightA = nums1[startA];
        }

        if(startB < n){
            rightB = nums2[startB];
        }

        int minRight = Math.min(rightA, rightB);

        if((m + n) % 2 == 0){
            res = (minRight + maxLeft) / 2.0;
        }else{
            res = Math.max(minRight, maxLeft);
        }

        return res;

    }


    /**
     * @author zlx
     * @desc 33. 搜索旋转排序数组 middle
     * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
     *
     * ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
     *
     * 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
     *
     * 你可以假设数组中不存在重复的元素。
     *
     * 你的算法时间复杂度必须是 O(log n) 级别。
     *
     * 示例 1:
     *
     * 输入: nums = [4,5,6,7,0,1,2], target = 0
     * 输出: 4
     * 示例 2:
     *
     * 输入: nums = [4,5,6,7,0,1,2], target = 3
     * 输出: -1
     * @date 10:40 2020-05-06
     * @param nums
     * @param  target
     * @return int
     **/
    public int search(int[] nums, int target) {

       Map<Integer, Integer> map = new HashMap<>();
       for(int i = 0;i < nums.length;i++){
           map.put(nums[i], i);
       }
       if(map.containsKey(target)){
           return map.get(target);
       }else{
           return -1;
       }
    }


    
    /**
     * medium
     * @author zlx
     * @desc 面试题 01.07. 旋转矩阵
     * 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
     *
     * 不占用额外内存空间能否做到？
     *
     *
     *
     * 示例 1:
     *
     * 给定 matrix =
     * [
     *   [1,2,3],
     *   [4,5,6],
     *   [7,8,9]
     * ],
     *
     * 原地旋转输入矩阵，使其变为:
     * [
     *   [7,4,1],
     *   [8,5,2],
     *   [9,6,3]
     * ]
     * 示例 2:
     *
     * 给定 matrix =
     * [
     *   [ 5, 1, 9,11],
     *   [ 2, 4, 8,10],
     *   [13, 3, 6, 7],
     *   [15,14,12,16]
     * ],
     *
     * 原地旋转输入矩阵，使其变为:
     * [
     *   [15,13, 2, 5],
     *   [14, 3, 4, 1],
     *   [12, 6, 8, 9],
     *   [16, 7,10,11]
     * ]
     * @date 20:43 2020-04-07
     *  解题思路： 经过90度旋转 a[i][j] 第i行第j列的数字转到 第j行，第（N-1-i）列
     * @param
     * @return void
     **/
    public void rotate(int[][] matrix) {

        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return ;

        int n = matrix.length;
        int tmp = 0;
        for(int i = 0;i < n/2;i++){
            for(int j = 0;j < (n + 1)/2;j++){
                tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];
                matrix[j][n - 1 - i] = tmp;
            }
        }
    }



    /**
     * @author zlx
     * medium
     * @desc 289. 生命游戏
     * 根据 百度百科 ，生命游戏，简称为生命，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。
     *
     * 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
     *
     * 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
     * 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
     * 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
     * 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
     * 根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
     *
     *
     *
     * 示例：
     *
     * 输入：
     * [
     *   [0,1,0],
     *   [0,0,1],
     *   [1,1,1],
     *   [0,0,0]
     * ]
     * 输出：
     * [
     *   [0,0,0],
     *   [1,0,1],
     *   [0,1,1],
     *   [0,1,0]
     * ]
     *
     * 解题思路：方法一：复制一个数组，进行操作；
     *          方法二： 在同一个数组进行操作，但是0->1 用2， 1->0 用-2表示，既可以看道旧状态，还可以看到新状态
     * @date 21:34 2/020-04-02
     * @param board
     * @return void
     **/
    public void gameOfLife(int[][] board) {

        int m = board.length;
        int n = board[0].length;
        int [][] copyBoard = new int[m][n];
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                copyBoard[i][j] = board[i][j];
            }
        }

        int [][] directions = {{0,1}, {1,1}, {1,0}, {1,-1}, {0, -1}, {-1,-1}, {-1, 0}, {-1, 1}};

        for(int i = 0;i < m;i ++){
            for(int j = 0;j < n;j++){
                int val = copyBoard[i][j];
                int liveNum = countLive(copyBoard, directions, i, j);
                System.out.println("i=" + i + "  j=" + j + "  liveCOunt:" + liveNum);
                if(val == 1){
                    if(liveNum != 2 && liveNum != 3){
                        board[i][j] = 0;
                    }
                }else{
                    if(liveNum == 3){
                        board[i][j] = 1;
                    }
                }
            }
        }
    }

    public int countLive(int [][] input, int [][] direction, int x, int y){
        int liveNums = 0;
        for(int i = 0;i < 8;i++){
            int tmpX = x + direction[i][0];
            int tmpY = y + direction[i][1];
            if(tmpX >= 0 && tmpX < input.length && tmpY >= 0 && tmpY < input[0].length){
                if(input[tmpX][tmpY] == 1){
                    liveNums ++;
                }
            }
        }
        return liveNums;
    }



    /**
     * easy
     * * 914. 卡牌分组
     * 给定一副牌，每张牌上都写着一个整数。
     *
     * 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
     *
     * 每组都有 X 张牌。
     * 组内所有的牌上都写着相同的整数。
     * 仅当你可选的 X >= 2 时返回 true。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[1,2,3,4,4,3,2,1]
     * 输出：true
     * 解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]
     * 示例 2：
     *
     * 输入：[1,1,1,2,2,2,3,3]
     * 输出：false
     * 解释：没有满足要求的分组。
     * 示例 3：
     *
     * 输入：[1]
     * 输出：false
     * 解释：没有满足要求的分组。
     * 示例 4：
     *
     * 输入：[1,1]
     * 输出：true
     * 解释：可行的分组是 [1,1]
     * 示例 5：
     *
     * 输入：[1,1,2,2,2,2]
     * 输出：true
     * 解释：可行的分组是 [1,1]，[2,2]，[2,2]
     *
     * 解题思路： 利用HashMap计算各张排的数量，然后求最小公约数， 最小公约数>=2 即正确 || 求最大公约数 >=2 即正确
     * @param deck
     * @return
     */
    public boolean hasGroupsSizeX(int[] deck) {

        if(deck == null || deck.length <= 1){
            return false;
        }

        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        Map<Integer, Integer> map = new HashMap<>();
        for(int tmp : deck){
            if(map.containsKey(tmp)){
                map.put(tmp, map.get(tmp) + 1);
            }else{
                map.put(tmp,  1);
            }
        }
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            min = min < entry.getValue() ? min : entry.getValue();
            max = max > entry.getValue() ? max : entry.getValue();
        }
        if(min <= 1){
            return false;
        }
        boolean res = false;

        for(int i = 2; i <= max;i++){
            res = true;
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
               if(entry.getValue() % i != 0){
                   res = false;
                   break;
               }
            }
            if(res){
                return res;
            }
        }
        return false;

    }


    /**
     * @desc 求解最大公约数
     * @param a
     * @param b
     * @return
     */
    public static int getGCD(int a , int b){
        if(a < 0 || b < 0){
            return -1;
        }
        if(b == 0){
            return a;
        }
        return a % b == 0 ? b :getGCD(b, a % b);
    }

    /**
     * 892. 三维形体的表面积
     *
     * easy
     * 在 N * N 的网格上，我们放置一些 1 * 1 * 1  的立方体。
     *
     * 每个值 v = grid[i][j] 表示 v 个正方体叠放在对应单元格 (i, j) 上。
     *
     * 请你返回最终形体的表面积。
     *
     *
     *
     * 示例 1：
     *
     * 输入：[[2]]
     * 输出：10
     * 示例 2：
     *
     * 输入：[[1,2],[3,4]]
     * 输出：34
     * 示例 3：
     *
     * 输入：[[1,0],[0,2]]
     * 输出：16
     * 示例 4：
     *
     * 输入：[[1,1,1],[1,0,1],[1,1,1]]
     * 输出：32
     * 示例 5：
     *
     * 输入：[[2,2,2],[2,1,2],[2,2,2]]
     * 输出：46
     * @param grid
     * @return
     */
    public int surfaceArea(int[][] grid) {

        if(grid == null || grid.length == 0){
            return 0;
        }

        int res = 0;
        for(int i = 0;i < grid.length;i++){
            for(int j = 0;j < grid[0].length;j++){
                //前面
                res += i-1 >= 0 ? Math.max(grid[i][j] - grid[i-1][j], 0) : grid[i][j];
                //后面
                res += i+1 < grid.length ? Math.max(grid[i][j] - grid[i+1][j], 0) : grid[i][j];
                //左面
                res += j-1 >= 0 ? Math.max(grid[i][j] - grid[i][j - 1], 0) : grid[i][j];
                //右面
                res += j+1 < grid[0].length ? Math.max(grid[i][j] - grid[i][j+1], 0) : grid[i][j];
                //上下两面
                res += 2 * (grid[i][j] > 0 ? 1 :0);
            }
        }
        return res;
    }


    /**
     * easy
     * 169. 多数元素
     * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
     *
     * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     *
     * 示例 1:
     *
     * 输入: [3,2,3]
     * 输出: 3
     * 示例 2:
     *
     * 输入: [2,2,1,1,1,2,2]
     * 输出: 2
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {


        Map<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        for(int num : nums){
            if(map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            }else{
                map.put(num, 1);
            }
            if(map.get(num) > len / 2){
                return  num;
            }
        }
        return 0;
    }


    /**
     * 167. 两数之和 II - 输入有序数组
     *
     * 给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
     *
     * 函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
     *
     * 说明:
     *
     * 返回的下标值（index1 和 index2）不是从零开始的。
     * 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
     * 示例:
     *
     * 输入: numbers = [2, 7, 11, 15], target = 9
     * 输出: [1,2]
     * 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param numbers
     * @param target
     * @return
     */
    public static int[] twoSum167(int[] numbers, int target) {

        int [] res = new int[2];
        int left = 1, right = numbers.length;
        while (left != right){

            int tmp = numbers[left - 1] + numbers[right - 1];
            if( tmp == target){
                break;
            } else if(tmp > target){
                right --;
            } else {
                left ++;
            }
        }
        if(left != right){
            res[0] = left;
            res[1] = right;
        }
        return res;
    }

    /**
     * 1013. 将数组分成和相等的三个部分
     * easy
     * 给你一个整数数组 A，只有可以将其划分为三个和相等的非空部分时才返回 true，否则返回 false。
     *
     *
     * 形式上，如果可以找出索引 i+1 < j 且满足 (A[0] + A[1] + ... + A[i] == A[i+1] + A[i+2] + ... + A[j-1] == A[j] + A[j-1] + ... + A[A.length - 1]) 就可以将数组三等分。
     *
     *  
     *
     * 示例 1：
     *
     * 输出：[0,2,1,-6,6,-7,9,1,2,0,1]
     * 输出：true
     * 解释：0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1
     * 示例 2：
     *
     * 输入：[0,2,1,-6,6,7,9,-1,2,0,1]
     * 输出：false
     * 示例 3：
     *
     * 输入：[3,3,6,5,-2,2,5,1,-9,4]
     * 输出：true
     * 解释：3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param A
     * @return
     */
    public boolean canThreePartsEqualSum(int[] A) {

        if(A== null || A.length <= 2){
            return false;
        }
        int sum = 0;
        for(int a: A){
            sum += a;
        }

        if(sum % 3 != 0){
            return false;
        }

        int temp = sum / 3;
        int left = 0, leftSum = A[left], right = A.length - 1, rightSum = A[right];
        while (left + 1 < right){

            if(leftSum == temp && rightSum == temp){
                return true;
            }
            if(leftSum != temp) {
                left++;
                leftSum += A[left];
            }
            if(rightSum != temp) {
                right--;
                rightSum += A[right];
            }
        }
        return false;
    }

    /**
     * 45. 跳跃游戏 II
     * 给定一个非负整数数组，你最初位于数组的第一个位置。
     *
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     *
     * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     *
     * 示例:
     *
     * 输入: [2,3,1,1,4]
     * 输出: 2
     * 解释: 跳到最后一个位置的最小跳跃数是 2。
     *      从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
     * 说明:
     *
     * 假设你总是可以到达数组的最后一个位置。
     *
     * @param nums
     * @return
     */
    public static int jump(int[] nums) {


        //return jumpSolutionI(nums);
        return jumpSolutionII(nums);
    }


    /**
     * 解法一：
     * 运行会超出时间限制
     * @param nums
     * @return
     */
    public static int jumpSolutionI(int [] nums){

        if(nums == null){
            return 0;
        }
        int dp [] = new int[nums.length];
        for(int i =1;i < nums.length;i++){
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;

        for(int i = 1; i < nums.length;i++){
            for(int j = i - 1; j >= 0;j--){
                if(j + nums[j] >= i){
                    dp[i] = Math.min(dp[j]+ 1, dp[i]);
                }
            }
        }
        return dp[nums.length - 1];
    }


    /**
     * 解法二：基于贪心算法求解
     * @param nums
     * @return
     */
    public static int jumpSolutionII(int [] nums){

        if(nums == null || nums.length <= 0){
            return 0;
        }

        int jumps = 0, curEnd = 0, curFarthest = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            curFarthest = Math.max(curFarthest, i + nums[i]);
            if (i == curEnd) {
                jumps++;
                curEnd = curFarthest;
            }
        }
        return jumps;

    }




    /**
     * 55. 跳跃游戏
     * 给定一个非负整数数组，你最初位于数组的第一个位置。
     *
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     *
     * 判断你是否能够到达最后一个位置。
     *
     * 示例 1:
     *
     * 输入: [2,3,1,1,4]
     * 输出: true
     * 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
     * 示例 2:
     *
     * 输入: [3,2,1,0,4]
     * 输出: false
     * 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
     * @param nums
     * @return
     */
    public static boolean canJump(int[] nums) {

        if (nums == null || nums.length == 0) {
            return false;
        }
        count = 0;
         dfsCanJump(nums, 0, nums.length);
         return count >=1;
    }

    public static  int count = 0;


    /**
     * 解法一： 基于dfs求解
     * @param nums
     * @param pos
     * @param len
     */
    public static void dfsCanJump(int[] nums, int pos, int len){

        System.out.println("pos=====" + pos);
        if(pos == (len - 1)){
            count++;
            return;
        }

        if(pos >= len || (nums[pos] == 0 && pos != (len - 1))){
            System.out.println("======dfs start=====");
            return;
        }

        for(int i = 1; i <= nums[pos]; i++) {
            System.out.println("i====" + i);
            dfsCanJump(nums, pos + i, len);
        }

        System.out.println("----------------------------------------");
    }

    /**
     * 解法二：基于回溯法进行判断
     * @param position
     * @param nums
     * @return
     */
    public boolean canJumpFromPosition(int position, int[] nums) {


        if (position == nums.length - 1) {
            return true;
        }
        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) {
                return true;
            }
        }

        return false;
    }


    enum Index{

        GOOD, BAD, UNKNOW;
    }
    /**
     * 解法三：自底向上的动态规划
     * 时间复杂度O(n^2), 空间复杂度O(n)
     * @param nums
     * @return
     */
    public boolean canJumpFromPositionIII(int [] nums){


        Index [] flag = new Index[nums.length];
        for(int i =0;i < nums.length;i++){
            flag[i] = Index.UNKNOW;
        }
        flag[nums.length - 1] = Index.GOOD;
        for(int i = nums.length - 2; i>=0;i--){

            int furthestJump = Math.min(i + nums[i], nums.length - 1);

            for(int j = i+1; j <= furthestJump;j++){

                if(flag[j] == Index.GOOD){
                    flag[i] = Index.GOOD;
                    break;
                }
            }
        }
        return flag[0] == Index.GOOD;

    }


    /**
     * 解法四： 基于自底向上的动态规划，改成贪心算法,
     * 只要节点i能跳到'最后'一个位置，该点给被认为是GOOD点
     * 时间复杂度O(n), 空间复杂度O(1)
     * @param nums
     * @return
     */
    public boolean canJumpFromPositionIV(int [] nums){

        int lastPos = nums.length - 1;
        for(int i = nums.length - 1;i >= 0;i--){

            if(i + nums[i] >= lastPos){
                lastPos = i;
            }
        }
        return lastPos == 0;
    }


    /**
     * 200. 岛屿数量
     * 给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
     *
     * 示例 1:
     *
     * 输入:
     * 11110
     * 11010
     * 11000
     * 00000
     *
     * 输出: 1
     * 示例 2:
     *
     * 输入:
     * 11000
     * 11000
     * 00100
     * 00011
     *
     * 输出: 3
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/number-of-islands
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param grid
     * @return
     */
    public static int numIslands(char[][] grid) {

        if(grid == null || (grid.length == 0)){
            return 0;
        }

        int [][] directions = {{0, 1}, {1, 0},{0, -1},{-1, 0}};
        int [][] flag = new int[grid.length][grid[0].length];
        int count = 0;
        int row = grid.length;
        int col = grid[0].length;

        for(int i = 0;i < row;i++){
            for(int j = 0; j < col;j++){
                if(grid[i][j] == '1' && flag[i][j] == 0){
                    count ++;
                    dfsNumIsland(grid, flag, directions, i, j, row, col);

                }
            }
        }
        return count;
    }

    /**
     * 基于DFS进行求解
     * @param grid
     * @param flag
     * @param directions
     * @param x
     * @param y
     * @param row
     * @param col
     */
    public static void dfsNumIsland(char [][] grid, int [][] flag, int[][] directions, int x, int y, int row, int col){

        flag[x][y] = 1;
        for(int i =0;i < 4;i++){

            int tmpX = x + directions[i][0];
            int tmpY = y + directions[i][1];
            if(tmpX >= 0 && tmpX < row && tmpY >= 0 && tmpY < col){
                if(grid[tmpX][tmpY] == '1' && flag[tmpX][tmpY] == 0){
                    dfsNumIsland(grid, flag, directions, tmpX, tmpY, row, col);
                }
            }
        }
    }


    /**
     * 200. 岛屿数量
     * 基于BFS进行求解
     * @param grid
     * @return
     */
    public static int numIslandsSolutionII(char[][] grid) {

        if(grid == null || (grid.length == 0)){
            return 0;
        }

        int [][] directions = {{0, 1}, {1, 0},{0, -1},{-1, 0}};
        int [][] flag = new int[grid.length][grid[0].length];
        int count = 0;
        int row = grid.length;
        int col = grid[0].length;
        Integer [][] pos = new Integer[1][2];
        for(int i = 0;i < row;i++){
            for(int j = 0; j < col;j++){
                if(grid[i][j] == '1' && flag[i][j] == 0){
                    count++;
                    flag[i][j] = 1;
                    LinkedList<Integer[][]> queue = new LinkedList<>();
                    pos[0][0] = i;
                    pos[0][1] = j;
                    queue.add(pos);
                    while (!queue.isEmpty()) {
                        pos  = queue.removeFirst();
                        for (int z = 0; z < 4; z++) {
                            int tmpX = pos[0][0] + directions[z][0];
                            int tmpY = pos[0][1] + directions[z][1];
                            if (tmpX >= 0 && tmpX < row && tmpY >= 0 && tmpY < col) {

                                if (grid[tmpX][tmpY] == '1' && flag[tmpX][tmpY] == 0) {

                                    Integer [][] tmpPos = new Integer[1][2];
                                    tmpPos[0][0] = tmpX;
                                    tmpPos[0][1] = tmpY;
                                    flag[tmpX][tmpY] = 1;
                                    queue.addLast(tmpPos);
                                }
                            }

                        }
                    }
                }

            }
        }
        return count;
    }



    public static int numIslandsIIIII(char[][] grid) {
        //           x-1,y
        //  x,y-1    x,y      x,y+1
        //           x+1,y
        //int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        int [][] directions = {{0, 1}, {1, 0},{0, -1},{-1, 0}};
        int rows = grid.length;
        if (rows == 0) {
            return 0;
        }
        int cols = grid[0].length;
        boolean[][] marked = new boolean[rows][cols];
        int count = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 如果是岛屿中的一个点，并且没有被访问过
                // 从坐标为 (i,j) 的点开始进行广度优先遍历
                if (!marked[i][j] && grid[i][j] == '1') {
                    count++;
                    LinkedList<Integer> queue = new LinkedList<>();
                    // 小技巧：把坐标转换为一个数字
                    // 否则，得用一个数组存，在 Python 中，可以使用 tuple 存
                    queue.addLast(i * cols + j);
                    // 注意：这里要标记上已经访问过
                    marked[i][j] = true;
                    while (!queue.isEmpty()) {
                        int cur = queue.removeFirst();
                        int curX = cur / cols;
                        int curY = cur % cols;
                        // 得到 4 个方向的坐标
                        for (int k = 0; k < 4; k++) {
                            int newX = curX + directions[k][0];
                            int newY = curY + directions[k][1];
                            System.out.println("tmpX====" + newX + "   tmpY===" + newY);
                            // 如果不越界、没有被访问过、并且还要是陆地，我就继续放入队列，放入队列的同时，要记得标记已经访问过
                            if (inArea(newX, newY, rows, cols) && grid[newX][newY] == '1' && !marked[newX][newY]) {
                                queue.addLast(newX * cols + newY);
                                // 【特别注意】在放入队列以后，要马上标记成已经访问过，语义也是十分清楚的：反正只要进入了队列，你迟早都会遍历到它
                                // 而不是在出队列的时候再标记
                                // 【特别注意】如果是出队列的时候再标记，会造成很多重复的结点进入队列，造成重复的操作，这句话如果你没有写对地方，代码会严重超时的
                                marked[newX][newY] = true;
                            }
                        }
                    }
                }
            }

        }
        return count;
    }

    private static boolean inArea(int x, int y, int rows, int cols) {
        // 等于号这些细节不要忘了
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }



    public static int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        for(int i = 0;i < nums.length;i++){
            System.out.print(nums[i] + "    ");
        }
        System.out.println();
        return nums[nums.length - k];
    }


    /**
     * 1283. 使结果不超过阈值的最小除数
     * 给你一个整数数组 nums 和一个正整数 threshold  ，你需要选择一个正整数作为除数，然后将数组里每个数都除以它，并对除法结果求和。
     *
     * 请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。
     *
     * 每个数除以除数后都向上取整，比方说 7/3 = 3 ， 10/2 = 5 。
     *
     * 题目保证一定有解。
     *
     *  思路： x/divide 向上取整， 除数越小，商总和越大；除数越大，商总和越小；
     *        当除数>= 数组最大值MAX， 最小商总和和=数组长度Len； 最大商总和=数组数据之和；
     *
     *
     *
     *        由于： 要求小于等于阈值 threshold 的除数中 最小 的那个， 因为，可以使用2分查找， 当商总和>threshold, 除数要变大；当商总和<threshold, 除数要变小；
     *
     * 示例 1：
     *
     * 输入：nums = [1,2,5,9], threshold = 6
     * 输出：5
     * 解释：如果除数为 1 ，我们可以得到和为 17 （1+2+5+9）。
     * 如果除数为 4 ，我们可以得到和为 7 (1+1+2+3) 。如果除数为 5 ，和为 5 (1+1+1+2)。
     * 示例 2：
     *
     * 输入：nums = [2,3,5,7,11], threshold = 11
     * 输出：3
     * 示例 3：
     *
     * 输入：nums = [19], threshold = 5
     * 输出：4
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/find-the-smallest-divisor-given-a-threshold
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param nums
     * @param threshold
     * @return
     */
    public static int smallestDivisor(int[] nums, int threshold) {

        Arrays.sort(nums);
        int left = 1, right = nums[nums.length - 1];
        while(left < right){

            int mid = (left + right) / 2;
            int tmpThreshold = 0;
            for(int tmp : nums){
                tmpThreshold += Math.ceil(tmp / (mid * 1.0 ));
            }
            if(tmpThreshold > threshold){
                left = mid + 1;
            }else{
                right = mid;
            }
            //System.out.println("left: " + left + "    right: =----" + right + "   tmpThreshold is:===" + tmpThreshold);
        }
        return left;

    }


    /**
     * 322. 零钱兑换
     * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
     *
     * 示例 1:
     *
     * 输入: coins = [1, 2, 5], amount = 11
     * 输出: 3
     * 解释: 11 = 5 + 5 + 1
     * 示例 2:
     *
     * 输入: coins = [2], amount = 3
     * 输出: -1
     *
     * 背包算法， dp[i]表示总金额为i时， 最少的硬币组成数量
     *
     * 说明:
     * 你可以认为每种硬币的数量是无限的。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/coin-change
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param coins
     * @param amount
     * @return
     */
    public static int  coinChange(int[] coins, int amount) {

       int [] dp = new int[amount + 1];
       for(int i = 1;i <= amount;i++){
           dp[i] = amount+1;
       }

       for(int i = 1; i<= amount;i++){
           for(int j = 0;j < coins.length;j++){

               if(coins[j] <= i){
                   dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
               }
           }
       }
        System.out.println(Arrays.toString(dp));
       return dp[amount] > amount ? -1 : dp[amount];

    }


    /**
     *
     * 207. 课程表 middle
     * 现在你总共有 n 门课需要选，记为 0 到 n-1。
     *
     * 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
     *
     * 给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
     *
     * 示例 1:
     *
     * 输入: 2, [[1,0]]
     * 输出: true
     * 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
     * 示例 2:
     *
     * 输入: 2, [[1,0],[0,1]]
     * 输出: false
     * 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
     * 说明:
     *
     * 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
     * 你可以假定输入的先决条件中没有重复的边。
     * 提示:
     *
     * 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
     * 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
     * 拓扑排序也可以通过 BFS 完成。
     * @param numCourses
     * @param prerequisites
     *
     *
     * @return
     */
    public static boolean canFinish(int numCourses, int[][] prerequisites) {

        int [][] adjacency = new int [numCourses][numCourses];
        for(int i = 0; i< prerequisites.length;i++){
            adjacency[prerequisites[i][1]][prerequisites[i][0]] = 1;
        }
        int [] flag = new int [numCourses];
        for(int i = 0;i < numCourses;i++){
            if(!dfs(adjacency, flag, i)){
                return false;
            }
        }
        return true;
    }


    /**
     * 解法一： 利用DFS判断图是否有环，
     * （1）借助标识数组flag :
     *         flag[i] = 0 未被访问；
     *         flag[i] = -1 已被其他节点启动的DFS访问过；
     *         flag[i] = 1 已被当前节点启动的DFS访问过；
     * （2）对 numCourses 个节点依次执行 DFS，判断每个节点起步 DFS 是否存在环，若存在环直接返回 FalseFalse。DFS 流程；
     * 终止条件：
     * 当 flag[i] == -1，说明当前访问节点已被其他节点启动的 DFS 访问，无需再重复搜索，直接返回 TrueTrue。
     * 当 flag[i] == 1，说明在本轮 DFS 搜索中节点 i 被第 22 次访问，即 课程安排图有环，直接返回 FalseFalse。
     * （3）将当前访问节点 i 对应 flag[i] 置 11，即标记其被本轮 DFS 访问过；
     * （4）递归访问当前节点 i 的所有邻接节点 j，当发现环直接返回 False；
     * （5）当前节点所有邻接节点已被遍历，并没有发现环，则将当前节点 flag 置为 -1−1 并返回 TrueTrue。
     * （6）若整个图 DFS 结束并未发现环，返回 TrueTrue。
     *
     * @param adjacency
     * @param flag
     * @param i
     * @return
     */
    public static boolean dfs(int [][] adjacency, int [] flag, int i ){

        if(flag[i] == 1){
            return false;
        }
        if(flag[i] == -1){
            return true;
        }
        flag[i] = 1;
        for(int j = 0; j < adjacency[0].length;j++){
            if(adjacency[i][j] == 1 && !dfs(adjacency, flag, j)){
                return false;
            }
        }
        flag[i] = -1;
        return true;
    }


    /**
     *
     * 287. 寻找重复数
     * 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
     *
     * 示例 1:
     *
     * 输入: [1,3,4,2,2]
     * 输出: 2
     * 示例 2:
     *
     * 输入: [3,1,3,4,2]
     * 输出: 3
     * 说明：
     *
     * 不能更改原数组（假设数组是只读的）。
     * 只能使用额外的 O(1) 的空间。
     * 时间复杂度小于 O(n2) 。
     * 数组中只有一个重复的数字，但它可能不止重复出现一次。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/find-the-duplicate-number
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param nums
     * @return
     */
    public int findDuplicate(int[] nums) {

        if(nums == null || nums.length <= 1){
            return -1;
        }

        int slow = nums[0], fast = nums[nums[0]];

        //找到交叉点
        while (slow != fast){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

        fast = 0;
        while (fast != slow){
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;

    }

    /**
     * 75. 颜色分类
     *
     * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
     *
     * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
     *
     * 注意:
     * 不能使用代码库中的排序函数来解决这道题。
     *
     * 示例:
     *
     * 输入: [2,0,2,1,1,0]
     * 输出: [0,0,1,1,2,2]
     * 进阶：
     *
     * 一个直观的解决方案是使用计数排序的两趟扫描算法。
     * 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
     * 你能想出一个仅使用常数空间的一趟扫描算法吗？
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/sort-colors
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param nums
     */
    public void sortColors(int[] nums) {

        int cur = 0, start = 0, end = nums.length - 1;
        while (cur <= end){

            if(nums[cur] == 0){

                nums[cur] = nums[start];
                nums[start] = 0;
                start ++;
                cur ++;
            }else if(nums[cur] == 2){

                nums[cur] = nums[end];
                nums[end] = 2;
                end --;

            }else{
                cur++;
            }
        }
    }


    /**
     * 78. 子集
     * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     *
     * 说明：解集不能包含重复的子集。
     *
     * 示例:
     *
     * 输入: nums = [1,2,3]
     * 输出:
     * [
     *   [3],
     *   [1],
     *   [2],
     *   [1,2,3],
     *   [1,3],
     *   [2,3],
     *   [1,2],
     *   []
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/subsets
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsets(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return res;
        }
        Arrays.sort(nums);
        List<Integer> tmp = new ArrayList<>();
        backtrack(res, tmp, nums, 0);
        return res;

    }


    public static void backtrack(List<List<Integer>> res, List<Integer> tmpList, int [] nums , int start){


        res.add(new ArrayList<>(tmpList));
        System.out.println("start=======" + start);
        for(int i = start;i < nums.length;i++){
            tmpList.add(nums[i]);
            backtrack(res, tmpList, nums, i+1);
            tmpList.remove(tmpList.size() - 1);
            System.out.println("tmpSize====" + tmpList + "   i===" + i);
        }

    }


    /**
     *
     * 在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。
     *
     * 「黑皇后」在棋盘上的位置分布用整数坐标数组 queens 表示，「白国王」的坐标用数组 king 表示。
     *
     * 「黑皇后」的行棋规定是：横、直、斜都可以走，步数不受限制，但是，不能越子行棋。
     *
     * 请你返回可以直接攻击到「白国王」的所有「黑皇后」的坐标（任意顺序）。
     *
     *  
     *
     * 示例 1：
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/queens-that-can-attack-the-king
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param queens
     * @param king
     * @return
     */
    public static List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {

        List<List<Integer>> res = new ArrayList<>();
        if(queens ==  null || king == null || queens[0].length !=2 || king.length != 2){
            return res;
        }
        boolean [][] flag = new boolean[8][8];


        for(int i = 0;i < queens.length;i++){
            flag[queens[i][0]][queens[i][1]] = true;
        }

        for(int i =0;i < 8;i++){
            for(int j = 0;j < 8;j++){
                System.out.print(flag[i][j] + "   ");
            }
            System.out.println();
        }
        int [][] directions = new int [][] {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}};

        int destRow = king[0];
        int destCol = king[1];

        for(int i =0; i< 8;i ++){

            int directionRow = directions[i][0];
            int directionCol = directions[i][1];

            for(int tmpRow = destRow, tmpCol = destCol; (tmpRow < 8 && tmpRow >=0 && tmpCol >= 0 && tmpCol <8); tmpRow += directionRow , tmpCol += directionCol){

                if(flag[tmpRow][tmpCol]){

                    res.add(Arrays.asList(tmpRow, tmpCol));
                    break;
                }
            }
        }
        return res;
    }



    /**
     * 1. 两数之和
     * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
     *
     * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {

        if(nums == null || nums.length <= 1){
            return null;
        }
        int [] res = new int[2];
        HashMap<Integer, Integer> map = new HashMap<>();

        for(int i= 0;i < nums.length;i++){
            map.put(nums[i], i);
        }

        for(int i = 0;i < nums.length;i++){

            if(map.containsKey(target - nums[i]) && map.get(target- nums[i]) != i){

                res[0] = i;
                res[1] = map.get(target - nums[i]);
                break;
            }
        }
        return res;

    }


    /**
     * 15. 三数之和
     * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
     *
     * 注意：答案中不可以包含重复的三元组。
     *
     * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
     *
     * 满足要求的三元组集合为：
     * [
     *   [-1, 0, 1],
     *   [-1, -1, 2]
     * ]
     *
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length <= 2){
            return res;
        }
        Arrays.sort(nums);
        List<Integer> resRow = new ArrayList<>();
        for(int i = nums.length - 1; i>= 2;i--){
            int left = 0;
            int right = i-1;
            while(left < right){

                int tmp = nums[left] + nums[right] + nums[i];
                if(tmp > 0){
                    right --;
                }else if(tmp < 0){
                    left ++;
                }else{
                    resRow = Arrays.asList(nums[left], nums[right], nums[i]);
                    if(!res.contains(resRow)){
                        res.add(resRow);
                    }
                    left ++;
                    right --;
                }
            }
        }
        return res;

    }


    /**
     * 16. 最接近的三数之和
     *
     * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
     *
     * 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
     *
     * 与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
     *
     * 解题思路：先进行排序，然后基于3个指针进行操作，最大值指针i, 从最大值开始， left=0， right=i-1， 三个值相加与target进行对比，小，则left++， 若大，right--；
     * @param nums
     * @param target
     * @return
     */
    public static int threeSumCloest(int [] nums, int target){

        int min = Integer.MAX_VALUE;
        Arrays.sort(nums);
        int pos1 = 0, pos2 = 0, pos3 = 0;
        for(int i = nums.length - 1; i >= 2;i--){
            int left = 0;
            int right = i -1;
            while(left < right){
                int tmpMinus = nums[left] + nums[right] + nums[i] - target;
                if(Math.abs(tmpMinus) <= min){
                    min = Math.abs(tmpMinus);
                    pos1 = left;
                    pos2 = right;
                    pos3 = i;
                }
                if(tmpMinus > 0){
                    right --;
                }else if(tmpMinus < 0){
                    left ++;
                }else{
                    return target;
                }
            }
        }
        return nums[pos1] + nums[pos2] + nums[pos3];
    }




    /**
     * 42. 接雨水  基于木桶理论
     * 解法一：双指针法
     * 水往地处流
     * @param height
     * @return
     */
    public static int trap(int [] height){

        if(height == null || height.length <= 2){
            return 0;
        }

        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int area = 0;
        while (left <= right){
            if(height[left] <= height[right]){

                if(height[left] >= leftMax){
                    leftMax = height[left];
                }else{
                    area += leftMax - height[left];
                }
                left++;
            }else{

                if(height[right] >= rightMax){
                    rightMax = height[right];
                }else {
                    area += rightMax - height[right];
                }
                right --;
            }
        }
        return area;
    }




    /**
     * 11. Container With Most Water
     * 暴力破解法，复杂度为n^2
     */
    public int maxArea(int[] height) {

        int maxArea = 0;
        for(int i = 1;i < height.length;i++){

            for(int j = i-1; j >=0;j--){
                if(height[i] >= height[j]){
                    maxArea = Math.max(maxArea, (i-j) * height[j]);
                }else{
                    maxArea = Math.max(maxArea, (i-j) * height[i]);
                }
            }
        }
        return maxArea;
    }

    /**
     * 11. Container With Most Water
     * 基于动态规划思想解题，最大面积 maxArea = Max（min(height[i],  [j]) * (j-i)）
     * 因此，height[i] < height[j] 的时候，小值移动
     */
    public int maxAreaSolution2(int[] height) {

        if(height == null || height.length <=1){
            return 0;
        }
        int i = 0, j = height.length - 1;
        int maxArea = 0;
        while(i < j){

            if(height[i] <= height[j]){

                maxArea = Math.max(maxArea, height[i] * (j - i));
                i++;
            }else{

                maxArea = Math.max(maxArea, height[j] * (j - i));
                j --;
            }
        }
        return maxArea;
    }

    /**
     *
     * @param A
     * @return
     */
    public static int[][] flipAndInvertImage(int[][] A) {

        if(A == null || A.length == 0 || A[0].length == 0){
            return A;
        }
        int [][] res = new int[A.length][A[0].length];
        int row = res.length;
        int col = res[0].length;
        for(int i =0;i < row;i++){
            if(col%2 != 0){
                res[i][col/2] = 1 - A[i][col/2];
            }
            for(int j = 0;j < A[0].length/2;j++){
                res[i][j] = 1 - A[i][col - 1 - j];
                res[i][col - 1 - j] = 1- A[i][j];
            }
        }
        return res;
    }


    /**
     * @author zlx
     * @Description 354. 俄罗斯套娃信封问题
     * 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
     *
     * 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
     *
     * 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
     *
     * 注意：不允许旋转信封。
     *
     *
     * 示例 1：
     *
     * 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
     * 输出：3
     * 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
     * 示例 2：
     *
     * 输入：envelopes = [[1,1],[1,1],[1,1]]
     * 输出：1
     *
     *
     * 提示：
     *
     * 1 <= envelopes.length <= 5000
     * envelopes[i].length == 2
     * 1 <= wi, hi <= 104
     *
     * 解题思路：先将信封按宽度从小到大排序，宽度相等的从大到小排序，然后使用动态规划, 每个信封i能包含的信封数量 dp[i] = max(dp[j] + 1) if(j >= 0 && j < i)
     * @Date 4/8/21
     * @Param [envelopes]
     * @return int
     **/
    public int maxEnvelopes(int[][] envelopes) {

        if(envelopes == null || envelopes.length == 0 || envelopes[0].length == 0){
            return 0;
        }
        //优先按照信封宽度从小到大排序，信封宽度相等，按照高度从大到小排序
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {

                if(o1[0] != o2[0]){
                    return o1[0] - o2[0];
                }else{
                    return o2[1] - o1[1];
                }
            }
        });

        //dp[i] 表示到i能套多少个信封
        int dp [] = new int[envelopes.length];
        Arrays.fill(dp, 1);

        int res = 1;
        for(int i = 1;i < envelopes.length;i++){

            for(int j = 0;j < i;j++){

                if(envelopes[i][1] > envelopes[j][1]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
